Построить треугольник с вершинами в трех из данных n точек, содержащий внутри как можно больше данных точек - Free Pascal - Ответ 3909737

uses crt,graph;
const nmax=50;
      t=0.001;{точность сравнения вещественных чисел}
{площадь треугольника по координаьам вершин}
function Plos(x1,y1,x2,y2,x3,y3:real):real;
begin
Plos:=abs((x1-x2)*(y3-y2)-(y1-y2)*(x3-x2))/2;
end;
{принадлежность точки треугольнику}
function Prin(x,y,x1,y1,x2,y2,x3,y3:real):boolean;
var s,s1,s2,s3:real;
begin
s:=Plos(x1,y1,x2,y2,x3,y3);
s1:=Plos(x,y,x1,y1,x2,y2);
s2:=Plos(x,y,x2,y2,x3,y3);
s3:=Plos(x,y,x1,y1,x3,y3);
Prin:=abs(s-s1-s2-s3)<=t;
end;
 
var a:array[1..nmax,1..2] of real;
    x,y,n,i,j,k,m,mx,imx,jmx,kmx,kv:integer;
    ms:real;
    s,s1,s2,s3:string;
begin
clrscr;
randomize;
repeat
write('Kolichestvo tochek ot 5 do ',nmax,' n=');
readln(n);
until n in [5..nmax];
initgraph(x,y,'');
for i:=1 to n do
 begin
  a[i,1]:=-10+20*random;{координаты}
  a[i,2]:=-10+20*random;
 end;
mx:=0; {макс кол-во точек внутри}
imx:=1;{номера вершин с минимальной разницей}
jmx:=2;
kmx:=3;
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;{количество внутри}
  for m:=1 to n do
  if not(m in [i,j,k])and {проверякм точки, не вершины треугольника}
  Prin(a[m,1],a[m,2],a[i,1],a[i,2],a[j,1],a[j,2],a[k,1],a[k,2]) then inc(kv);
  if kv>mx then
   begin
    mx:=kv;
    kmx:=k;
    jmx:=j;
    imx:=i;
   end;
  end;
ms:=(getmaxY-50)/20;{масштаб для перевода координат в экранные}
x:=getmaxX div 2;{центр}
y:=getmaxY div 2;
{треугольник}
setcolor(12);
setfillstyle(1,12); {вершины}
circle(x+round(ms*a[imx,1]),y-round(ms*a[imx,2]),3);
floodfill(x+round(ms*a[imx,1]),y-round(ms*a[imx,2]),12);
circle(x+round(ms*a[jmx,1]),y-round(ms*a[jmx,2]),3);
floodfill(x+round(ms*a[jmx,1]),y-round(ms*a[jmx,2]),12);
circle(x+round(ms*a[kmx,1]),y-round(ms*a[kmx,2]),3);
floodfill(x+round(ms*a[kmx,1]),y-round(ms*a[kmx,2]),12);
setcolor(12); {стороны}
line(x+round(ms*a[imx,1]),y-round(ms*a[imx,2]),x+round(ms*a[jmx,1]),y-round(ms*a[jmx,2]));
line(x+round(ms*a[imx,1]),y-round(ms*a[imx,2]),x+round(ms*a[kmx,1]),y-round(ms*a[kmx,2]));
line(x+round(ms*a[kmx,1]),y-round(ms*a[kmx,2]),x+round(ms*a[jmx,1]),y-round(ms*a[jmx,2]));
for i:=1 to n do
if not(i in [imx,jmx,kmx]) then
if Prin(a[i,1],a[i,2],a[imx,1],a[imx,2],a[jmx,1],a[jmx,2],a[kmx,1],a[kmx,2])then
  begin
   setcolor(9);
   setfillstyle(1,9);
   circle(x+round(ms*a[i,1]),y-round(ms*a[i,2]),2);{точки внутри}
   floodfill(x+round(ms*a[i,1]),y-round(ms*a[i,2]),9);
  end
else
  begin
   setcolor(10);
   setfillstyle(1,10);
   circle(x+round(ms*a[i,1]),y-round(ms*a[i,2]),2);{точки снаружи}
   floodfill(x+round(ms*a[i,1]),y-round(ms*a[i,2]),10);
  end;
readln
end.