L футів. У разі невиконання умови або перевитрати коштів архітектор може позбутися голови.
Ваше завдання допомогти бідному архітекторові. Ваше завдання написати програму, яка визначить мінімально можливу довжину стіни, якою можна оточити палац і при цьому виконати всі вимоги короля.
Перший рядок вхідного файлу містить 2 числа N (3 ВЈ N ВЈ 1000) - кількість кутів в будівлі палацу і L (1 ВЈ L ВЈ 1000) мінімальне відстань на яке стіна може наближатися до палацу. Наступні N рядків описують координати на поверхні землі кутів палацу, в порядку їх обходу за годинниковою стрілкою. Кожен рядок містить два цілих числа - X i і Y i , відокремлених пропуском (-10000 ВЈ X i , Y i ВЈ 10000), які описую координати кутів палацу в футах. Всі кути палацу різні, а сторони не мають інших спільних точок, крім кутових.
Запишіть у вихідний файл одне число, що визначає мінімальну довжину палацу в футах, що задовольняє умовою задачі. Відповідь має бути записаний у вигляді цілого числа, так як з речовими числами король не знайомий, проте округляти його слід так, щоб ціле число футів відрізнялося від справжньої відповіді менш, ніж на 8 дюймів (в 1 футеро 12 дюймів).
Приклад вхідного файлу
Вихідний файл
9 100
200 400
300 400
300 300
400300
400 400
500 400
500200
350200
200 200
1628
В
Рішення . Відповіддю на дану завдання буде довжина опуклої оболонки, збільшена на довжину кола з радіусом L і округлена до найближчого цілого.
Задача 2 . На площині задані N точок. Побудувати замкнуту ламану без самоперетинів і самокасаній, вершинами якої мають стати всі задані точки. ( Див, наприклад, [5] , аналогічна задача пропонувалася на кіровської обласній олімпіаді 2002р. ).
Рішення. Наступний малюнок проілюструє ідею одного з можливих способів рішення даної задачі:
В
2. Чисельне рішення геометричних задач
У ряді випадків при рішенні геометричних задач формули з обчислювальної геометрії можуть виявитися занадто громіздкими і призводять до вирішення нелінійних рівнянь. Тоді на допомогу можуть прийти чисельні (наближені) методи, що дозволяють вирішити задачу за необхідний час і з потрібною точністю. Такий підхід був продемонстрований в [6] при розгляді завдання "Фонтан" (її не слід плутати із завданням 6, наведеної нижче).
З чисельних методів найбільш часто вживаним є метод дихотомії (ділення навпіл). Розглянемо його на прикладі задачі XII Всеросійської олімпіади з інформатики.
Задача 3 . Розділ царства. p> Царство царя Гороха являє собою опуклий N -кутник, усередині якого розташовані K селищ. Цар вирішив заповісти двом своїм синам по півцарства, однакові за площі і з рівною кількістю селищ. Для цього він вимагає розділити царство однієї прямолінійної кордоном. p> Напишіть програму, будує кордон згідно царській волі. Якщо межа проходить через селище, то воно може бути або віднесено до одного з полуцарств, або розділене на два селища, які будуть віднесені до різних полуцарствам (при непарному K межа, природно, повинна розділити якесь із селищ).
Перший рядок вхідного файлу містить кількість вершин багатокутника N (3 п‚Ј пЂ N п‚Ј пЂ 50). У наступних N рядках задані координати вершин багатокутника, перераховані в порядку обходу контуру за годинниковою стрілкою. В ( N +2)-му рядку вказано кількість селищ K (0 п‚Ј K пЂ п‚Ј 100), а в наступних K рядках задані координати селищ. Всі координати - цілі числа, які не перевищують за модулем 10 6 . Розмірами селищ варто знехтувати.
У вихідний файл потрібно вивести координати будь-яких двох різних точок, через які слід провести кордон. Координати повинні бути виведені з 6 знаками після десяткової крапки. br/>
Приклад вхідного файлу
Приклад вихідного файлу
4
10 вересень
20 40
40 40
51 10
2
21 30
40 20
30.000000 35.000000
30.000000 15.000000
В
Рішення. Виберемо довільну точку на кордоні царства. Для пошуку прямої, що проходить через цю точку і ділить царство на дві рівні поки тільки за площею частини, зафіксуємо дві інші точки кордону, так, що пряма проведена через обрану і першу з фіксованих точок ділить царство на дві нерівні частини, причому ліва (або нижня для горизонтальної...
