Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений (с Pascal) - C (СИ)

Формулировка задачи:

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

Решение задачи: «Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений (с Pascal)»

Листинг программы

var a, b: array[1 100] of record 
x,y:integer; 
f:boolean 
end; 
min, m, j, k, n: integer; 
begin 
readln(n); 
for i:=1 to n do 
begin 
read(a[i].x, a[i].y); 
a[i].f:=false 
end; {ищем нижнюю правую точку} 
m:=1; 
for i:=2 to n do 
if a[i].y < a[m].y then m:=i else 
if (a[i].y = a[m].y) and 
(a[i].x > a[m].x) then m:=i; 
b[1]:=a[m]; 
a[m].f:=true; 
k:=1; 
repeat 
min:=1; {ищем первую еще свободную точку} 
while a[min].f do inc(min); {ищем очередную вершину выпуклой оболочки} 
for j:=1 to n do 
if (not a[j].f) and 
((a[min].x-b[k].x)*(a[j].y-b[k].y)- 
(a[j].x-b[k].x)*(a[min].y-b[k].y)<0) 
then min:=j else 
if (not a[j].f) and 
((a[min].x-b[k].x)*(a[j].y-b[k].y)- 
(a[j].x-b[k].x)*(a[min].y-b[k].y)=0) and 
(sqr(a[min].x-b[k].x)+sqr(a[min].y-b[k].y) > 
sqr(a[j].x-b[k].x)+sqr(a[j].y-b[k].y)) 
then min:=j; 
k:=k+1; 
a[min].f:=true; 
b[k]:=a[min] {записана очередная вершина} 
until min=m; {пока ломаная не замкнется} 
for j:=1 to k do {печать результата} 
writeln(b[j].x,' ',b[j].y); 
end.

Объяснение кода листинга программы

Объявлены переменные:
- a, b: массив из 100 записей, каждая из которых содержит поля x и y.
- x, y: целочисленные переменные.
- f: булева переменная.
- min, m, j, k, n: целочисленные переменные.
Считывается число n (количество вершин выпуклой оболочки).
В цикле считываются координаты вершин (x и y) и устанавливается флаг f в false.
Находится нижняя правая точка (вершина с наибольшим y при одинаковых x).
Устанавливается k=1 и начинается поиск вершин выпуклой оболочки:
- Считывается первая еще не помеченная вершина (min).
- Пока помеченного соседа нет, помечается текущая вершина и считывается следующая.
- Если помеченный сосед найден, он заменяет текущую вершину, и поиск продолжается.
- Если не помечен ни один сосед, текущая вершина помечается и поиск завершается.
Выводится результат - координаты вершин выпуклой оболочки.