Выбрать три различные точки из заданного множества - Pascal (80315)
Формулировка задачи:
Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами точек, лежащих внутри и вне треугольника, с вершинами в выбранных точках.
Решение задачи: «Выбрать три различные точки из заданного множества»
textual
Листинг программы
const e=0.01;{точность сравнения вещественных чисел}
type Point=record{тип точка}
x,y:real;
end;
{площадь треугольника}
function Strg(a,b,c:Point):real;
begin
Strg:=abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))/2;
end;
{принадлежит ли точка треугольнику}
function Prin(a,b,c,t:Point):boolean;
var s,s1,s2,s3:real;
begin
{площади 3х маленьких треугольников, образованных
двумя вершинами и точкой}
s1:=Strg(a,b,t);
s2:=Strg(a,c,t);
s3:=Strg(b,c,t);
{площадь самого треугольника}
s:=Strg(a,b,c);
Prin:=abs(s-(s1+s2+s3))>e;
end;
const nmax=15;{чтобы вошли в строку по щирине экрана}
var m:array[1..nmax] of Point;{множество точек}
n:integer;{его мощность}
kv,kn,kvmn,knmn:integer;{кол. точек в треугольнике и вне его}
mn,imn,jmn,kmn:integer;{номера вершин треугольника с минимальной разностью точек}
i,j,k,p:integer;{счетчики циклов}
begin
randomize;
repeat
write('Количество точек в множестве от 3 до ',nmax,' n=');
readln(n);
until n in [3..nmax];
writeln('Множество точек');
for i:=1 to n do
begin
m[i].x:=10*random;
m[i].y:=10*random;
end;
write(' ':2);
for i:=1 to n do
write(i:5);
writeln;
write('X:');
for i:=1 to n do
write(m[i].x:5:2);
writeln;
write('Y:');
for i:=1 to n do
write(m[i].y:5:2);
writeln;
writeln;
imn:=0;
jmn:=0;
kmn:=0;
mn:=n;
{перебираем треугольники }
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
begin
kv:=0;
kn:=0;
for p:=1 to n do
if not (p in [i,j,k]) then
if Prin(m[i],m[j],m[k],m[p]) then inc(kv)
else inc(kn);
if abs(kv-kn)<mn then
begin
mn:=abs(kv-kn);
imn:=i;
jmn:=j;
kmn:=k;
kvmn:=kv;
knmn:=kn;
end;
end;
writeln('Треугольник, у которого разница между количеством точек внутри и снаружи');
writeln('минимальна, образован точками:');
writeln(imn:2,'(',m[imn].x:5:2,';',m[imn].y:5:2,')');
writeln(jmn:2,'(',m[jmn].x:5:2,';',m[jmn].y:5:2,')');
writeln(kmn:2,'(',m[kmn].x:5:2,';',m[kmn].y:5:2,')');
writeln('Количество точек: внутри=',kvmn,' снаружи=',knmn);
end.
Объяснение кода листинга программы
- Объявляется константа
eс значением 0.01 для точности сравнения вещественных чисел. - Создается тип данных
Pointдля хранения координат точек на плоскости. - Описывается функция
Strgдля вычисления площади треугольника, принимающая три точки и возвращающая вещественное число. - Описывается функция
Prinдля определения принадлежности точки треугольнику, принимающая 4 точки (три для определения треугольника и одну для проверки) и возвращающая логическое значение. - Объявляются переменные:
m- массив точекn- количество точек в массивеkv,kn,kvmn,knmn- количество точек внутри и снаружи треугольникаmn,imn,jmn,kmn- номера вершин треугольника с минимальной разностью точекi,j,k,p- счетчики циклов
- Генерируется случайное количество точек от 3 до nmax, заполняется массив случайными координатами и выводится на экран.
- Находится треугольник с минимальной разностью количества точек внутри и снаружи с помощью вложенных циклов и вызова функций
Prin. - Выводится информация о треугольнике с минимальной разностью количества точек внутри и снаружи: его вершины, координаты и количество точек внутри и снаружи.