Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений (с Pascal) - C (СИ)
Формулировка задачи:
Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей. Напишите программу, строящую границу согласно царской воле. Если граница проходит через селение, то оно может быть либо отнесено к одному из полуцарств, либо разделено на два селения, которые будут отнесены к разным полуцарствам (при нечетном K граница, естественно, должна разделить какое-то из селений).
Знает кто как сделать?)
Решение задачи: «Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений (с Pascal)»
textual
Листинг программы
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).
- Пока помеченного соседа нет, помечается текущая вершина и считывается следующая.
- Если помеченный сосед найден, он заменяет текущую вершину, и поиск продолжается.
- Если не помечен ни один сосед, текущая вершина помечается и поиск завершается.
- Выводится результат - координаты вершин выпуклой оболочки.