Сайт підготовки до олімпіади з інформатики

(ДИВИСЬ ВКЛАДЕНИЙ ФАЙЛ)

Визначення площі довільного многокутника

За заданими координатами вершин многокутника визначити його площу.

Для обчислення площі можна використати формулу:

S=1/2*abs((x1*y2-x2*y1)+ (x2*y3-x3*y2)+..+ (xn*yn+1-xn+1*yn)), xn+1=x1; yn+1=y1.

Побудова опуклої оболонки для множини з N точок площини

Опуклою оболонкою деякої заданої множини точок називається перетин всіх опуклих множин, що містять задану множину. Для скінченої множини точок опуклою оболонкою буде завжди опуклий багатокутник, всі вершини якого є точками заданої множини.

Задача полягає в тому, щоб для заданої скінченої множини точок знайти вершини опуклої оболонки цієї множини. Будемо перераховувати вершини в порядку перегляду проти годинникової стрілки. Для ефективного розв’язування цієї задачі існує декілька різних алгоритмів. Наведемо найбільш просту реалізацію одного з них – алгоритму Джарвіса. Цей алгоритм інколи називають «загортання подарунка».

(ДИВИСЬ ВКЛАДЕНИЙ ФАЙЛ)

Задача 10. Task10 . Багатокутник на площині задано цілочисельними координатами своїх N вершин у декартовій системі координат. Потрібно знайти площу многокутника. Сторони багатокутника не стикаються (за винятком сусідніх - у вершинах) і не перетинаються.

введення

У першому рядку знаходиться число N. У наступних N рядках знаходяться пари чисел - координати точок. Якщо з'єднати точки в даному порядку, а також першу і останню точки, вийде заданий многокутник.

виведення

Вивести одне число - площа багатокутника. Його слід округлити до найближчого числа з однією цифрою після десяткової крапки.

обмеження

3 ≤ N ≤ 50 000, координати вершин цілі і по модулю не перевищують 20000.

Задача11.task11. Нова держава.

Іваном Річкоплавцем і його командою був відкритий новий багатий континент, який назвали Іванія, де вони вирішили оселитися. Кожним членом команди було засноване нове поселення і назване його іменем. Їхні нащадки вирішили утворити нову державу і побудувати кордон, таким чином щоб границя була мінімальної довжини у вигляді прямих відрізків, які з’єднають поселення, біля яких пройде кордон при умові, що в середині будуть всі інші поселення і площа країни буде найбільшою. Яка довжина границі утвореної держави і її площа?

Вхідні дані

В першому рядку знаходиться натуральне N (3<=N<=50) – число поселень. В наступних рядках координати кожного поселення X,Y, які записуються через пропуск. X,Y – цілі числа (-1000<=X<=1000; -1000<=Y<=1000).

Вихідні дані

В першому рядку Р, а в другому S. P i S – дійсні числа із виведеними двома розрядами після коми.

Максимальний час роботи 15 секунд