Сайт Андрея Зайчикова
|
|
Раздел царства
Царство царя Гороха представляет собой выпуклый N-угольник,
внутри которого расположены K селений. Царь решил завещать двум
своим сыновьям по полцарства, одинаковые по площади и с равным
количеством селений. Для этого он требует разделить царство
одной прямолинейной границей.
Hапишите программу, строящую границу согласно царской воле. Если граница проходит через селение, то оно может быть либо отнесено к одному из полуцарств, либо разделено на два селения, которые будут отнесены к разным полуцарствам (при нечетном K граница, естественно, должна разделить какое-то из селений).
Ввод:
Вывод:
Примечание:
Пример: 4 9 10 20 40 40 40 51 10 2 21 30 40 20Результат:
|
|