GPMB - Giải phóng mặt bằng
Tác giả: ladpro98
Ngôn ngữ: Pascal
program GPMB;
uses math;
const maxn=1700;
maxV=100;
fi='';
type e=record
x,y,s:longint;
end;
var f:array[-maxV..maxV,-maxV..maxV] of longint;
a,st:array[1..maxn] of e;
i,j,n,d,x,y,res,g,si:longint;
inp:text;
procedure sort(l,r:longint);
var i,j:longint;
t,p:e;
begin
if l>=r then exit;
i:=l;j:=r;
p:=a[random(r-l+1)+l];
repeat
while (a[i].x<p.x) or ((a[i].x=p.x) and (a[i].y<p.y)) do inc(i);
while (a[j].x>p.x) or ((a[j].x=p.x) and (a[j].y>p.y)) do dec(j);
if i<=j then begin
if i<j then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;
function gcd(a,b:longint):longint;
begin
if b=0 then exit(a);
if a mod b = 0 then exit(b);
exit(gcd(b, a mod b));
end;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
for i:=1 to n do readln(inp,a[i].x,a[i].y,a[i].s);
sort(1,n);
for i:=1 to n do begin
si:=sqr(a[i].s)+5;
res:=max(res,si);
for j:=1 to d do f[st[j].x,st[j].y]:=0;
d:=0;
for j:=1 to n do
if i<>j then
begin
x:=a[j].x-a[i].x;
y:=a[j].y-a[i].y;
g:=gcd(x,y);
x:=x div g;
y:=y div g;
if f[x,y]=0 then begin
inc(d);
st[d].x:=x;st[d].y:=y;
end;
inc(f[x,y],sqr(a[j].s)+5);
res:=max(res,si+f[x,y]);
end;
end;
write(res);
end.