Выбрать три различные точки из заданного множества - 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.

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

  1. Объявляется константа e с значением 0.01 для точности сравнения вещественных чисел.
  2. Создается тип данных Point для хранения координат точек на плоскости.
  3. Описывается функция Strg для вычисления площади треугольника, принимающая три точки и возвращающая вещественное число.
  4. Описывается функция Prin для определения принадлежности точки треугольнику, принимающая 4 точки (три для определения треугольника и одну для проверки) и возвращающая логическое значение.
  5. Объявляются переменные:
    • m - массив точек
    • n - количество точек в массиве
    • kv, kn, kvmn, knmn - количество точек внутри и снаружи треугольника
    • mn, imn, jmn, kmn - номера вершин треугольника с минимальной разностью точек
    • i, j, k, p - счетчики циклов
  6. Генерируется случайное количество точек от 3 до nmax, заполняется массив случайными координатами и выводится на экран.
  7. Находится треугольник с минимальной разностью количества точек внутри и снаружи с помощью вложенных циклов и вызова функций Prin.
  8. Выводится информация о треугольнике с минимальной разностью количества точек внутри и снаружи: его вершины, координаты и количество точек внутри и снаружи.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 3.9 из 5
Похожие ответы