0189. Американский пирог II

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	250 ms
Ограничение по памяти:	16 megabytes

Джиму и Стифлеру срочно понадобился яблочный пирог (каждому по пирогу), но у них только один пирог на двоих. Он имеет форму выпуклого многоугольника (т.е. все внутренние углы не более 180 градусов). Они сделали один прямолинейный разрез проходящий через точки (XA, YA) и (XB, YB). По одну сторону прямой осталось S1 ед2 верхней поверхности пирога, а по другую S2 (будем считать, что S1 ≥ S2, первый кусок достанется Стифлеру). Ваша задача найти S1 и S2.

Формат входного файла

В первой строке записано число N (2 < N < 51) - количество вершин у пирога. Далее в N строках заданы вершины своими координатами в порядке обхода по или против часовой стрелки. Возможно, что три или более точек лежит на одной прямой. В последних двух строках записаны координаты двух различных точек по которым проходит разрез. Все координаты задаются через пробел вещественными числами по модулю не превосходящими 10000. Количество знаков после запятой не превосходит 5. Возможно, что разрез не пройдет через пирог.

Формат выходного файла

Выведите S1 и S2 через пробел с 5 знаками после запятой.

Пример:

input.txt	output.txt
4 0 0 0 1 1 1 1 0 0.5 0 0.5 1	0.50000 0.50000

Источник: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Обсудить       Отправить решение



Версия для печати