Выбрать три различные точки из заданного множества - Pascal (80315)

Узнай цену своей работы

Формулировка задачи:

Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами точек, лежащих внутри и вне треугольника, с вершинами в выбранных точках.

Решение задачи: «Выбрать три различные точки из заданного множества»

textual
Листинг программы
  1. const e=0.01;{точность сравнения вещественных чисел}
  2. type Point=record{тип точка}
  3.            x,y:real;
  4.            end;
  5. {площадь треугольника}
  6. function Strg(a,b,c:Point):real;
  7. begin
  8. Strg:=abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))/2;
  9. end;
  10. {принадлежит ли точка треугольнику}
  11. function Prin(a,b,c,t:Point):boolean;
  12. var s,s1,s2,s3:real;
  13. begin
  14. {площади 3х маленьких треугольников, образованных
  15. двумя вершинами и точкой}
  16. s1:=Strg(a,b,t);
  17. s2:=Strg(a,c,t);
  18. s3:=Strg(b,c,t);
  19. {площадь самого треугольника}
  20. s:=Strg(a,b,c);
  21. Prin:=abs(s-(s1+s2+s3))>e;
  22. end;
  23.  
  24.  
  25. const nmax=15;{чтобы вошли в строку по щирине экрана}
  26.  
  27. var m:array[1..nmax] of Point;{множество точек}
  28.     n:integer;{его мощность}
  29.     kv,kn,kvmn,knmn:integer;{кол. точек в треугольнике и вне его}
  30.     mn,imn,jmn,kmn:integer;{номера вершин треугольника с минимальной разностью точек}
  31.     i,j,k,p:integer;{счетчики циклов}
  32. begin
  33. randomize;
  34. repeat
  35. write('Количество точек в множестве от 3 до ',nmax,' n=');
  36. readln(n);
  37. until n in [3..nmax];
  38. writeln('Множество точек');
  39. for i:=1 to n do
  40.  begin
  41.   m[i].x:=10*random;
  42.   m[i].y:=10*random;
  43.  end;
  44. write(' ':2);
  45. for i:=1 to n do
  46. write(i:5);
  47. writeln;
  48. write('X:');
  49. for i:=1 to n do
  50. write(m[i].x:5:2);
  51. writeln;
  52. write('Y:');
  53. for i:=1 to n do
  54. write(m[i].y:5:2);
  55. writeln;
  56. writeln;
  57. imn:=0;
  58. jmn:=0;
  59. kmn:=0;
  60. mn:=n;
  61. {перебираем треугольники }
  62. for i:=1 to n-2 do
  63. for j:=i+1 to n-1 do
  64. for k:=j+1 to n do
  65.  begin
  66.   kv:=0;
  67.   kn:=0;
  68.   for p:=1 to n do
  69.   if not (p in [i,j,k]) then
  70.   if Prin(m[i],m[j],m[k],m[p]) then inc(kv)
  71.   else inc(kn);
  72.   if abs(kv-kn)<mn then
  73.    begin
  74.     mn:=abs(kv-kn);
  75.     imn:=i;
  76.     jmn:=j;
  77.     kmn:=k;
  78.     kvmn:=kv;
  79.     knmn:=kn;
  80.    end;
  81.  end;
  82. writeln('Треугольник, у которого разница между количеством точек внутри и снаружи');
  83. writeln('минимальна, образован точками:');
  84. writeln(imn:2,'(',m[imn].x:5:2,';',m[imn].y:5:2,')');
  85. writeln(jmn:2,'(',m[jmn].x:5:2,';',m[jmn].y:5:2,')');
  86. writeln(kmn:2,'(',m[kmn].x:5:2,';',m[kmn].y:5:2,')');
  87. writeln('Количество точек: внутри=',kvmn,' снаружи=',knmn);
  88. 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

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы