Выбрать три различные точки из заданного множества - 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
. - Выводится информация о треугольнике с минимальной разностью количества точек внутри и снаружи: его вершины, координаты и количество точек внутри и снаружи.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д