Царство Царя Гороха или проблема с лабораторной работой

[Ivan.Rybin]

Ну что, ассы програмирования - есть головоломка! Дана нам на Программировании в институте такая вот лабработа:

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

Сделать нужно на Java, но суть в другом - а именно - в алгоритме. Кое-какое решение мы с Батей придумали, но возможно кто знает проще.

Все умные идеи\советы постить в тему, всем заранее спасибо!

ЗЫ: Повторяю - готовый код на Java я не прошу!

[NICK]

Старенькая задача из 12 Всероссийской олимпиады по информатике.
Ответа не знаю - слишком уж далек от программирования.
Но вот что нашел в инете, может поможет:

Входные данные

Первая строка входного файла содержит количество вершин многоугольника 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.000000 35.000000

30.000000 15.000000

[Ivan.Rybin]

увы, это было