Задача №112127. Раздел царства
Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей.
Напишите программу, строящую границу согласно царской воле. Если граница проходит через селение, то оно может быть либо отнесено к одному из полуцарств, либо разделено на два селения, которые будут отнесены к разным полуцарствам (при нечетном K граница, естественно, должна разделить какое-то из селений).
Первая строка входного файла содержит количество вершин многоугольника N (3 ≤ N ≤ 5000). В следующих N строках заданы координаты вершин многоугольника, перечисленные в порядке обхода контура по часовой стрелке. В (N + 2)-ой строке указано количество селений K (0 ≤ K ≤ 10000), а в последующих K строках заданы координаты селений. Все координаты - целые числа, не превосходящие по модулю 106. Размерами селений следует пренебречь
В выходной файл нужно вывести координаты любых двух различных точек, через которые следует провести границу. Координаты должны быть выведены с 6 знаками после десятичной точки.
4
9 10
20 40
40 40
51 10
2
21 30
40 20
30.000000 35.000000
30.000000 15.000000