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

Input file name:	input.txt
Output file name:	output.txt
Time limit:	250 ms
Memory limit:	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

Source: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Discuss       Submit a solution



Printable version