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