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.

Download