Главная
 Сайт Андрея Зайчикова
Вторник, 22 Июля 2003г. 
Карта сайта Поиск по сайту Написать письмо  
 .:Навигатор 
Новости
Библиотека
Статьи
Олимпиады
FAQ (ЧаВо)
Гостевая книга 
Ссылки
 .:Информация 


Раздел царства
Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей.
Hапишите программу, строящую границу согласно царской воле. Если граница проходит через селение, то оно может быть либо отнесено к одному из полуцарств, либо разделено на два селения, которые будут отнесены к разным полуцарствам (при нечетном K граница, естественно, должна разделить какое-то из селений).

Ввод:
Первая строка входного файла содержит количество вершин многоугольника N (3<=N<=50). В следующих N строках заданы координаты вершин многоугольника, перечисленные в порядке обхода контура по часовой стрелке. В (N+2)-ой строке указано количество селений K (0<=K<=100), а в последующих K строках заданы координаты селений. Все координаты -- целые числа, не превосходящие по модулю 106. Размерами селений следует пренебречь.

Вывод:
В выходной файл нужно вывести координаты любых двух различных точек, через которые следует провести границу. Координаты должны быть выведены с 6 знаками после десятичной точки.

Примечание:
Будут также оцениваться частичные решения для случая прямоугольного царства.

Пример:

4
9 10
20 40
40 40
51 10
2
21 30
40 20
Результат:
30.00000035.000000
30.00000015.000000

 .:Реклама 


 
 © Андрей Зайчиков