CASTLE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập thuật toán)

Code:

uses math;
const
    tfi='';//castle.inp';
    tfo='';//castle.out';
 
var
    fi,fo:text;
    n,top1,top2,top3,dem:longint;
    tg,kq1,kq2,kq11,kq22:int64;
    p,q,a,b:array[0..5001] of longint;
    st:array[0..5001] of int64;
procedure nhap;
    var i,j:longint;
    begin
        read(fi,n);
        for i:=1 to n do read(fi,a[i],b[i]);
        kq2:=high(int64);
    end;
 
procedure swap(var x,y:longint);
    var tg:longint;
    begin
        tg:=x;
        x:=y;
        y:=tg;
    end;
 
procedure sort(l,r:longint);
    var i,j,k,k1,k2:longint;
    begin
        i:=l;
        j:=r;
        k:=l+random(r-l+1);
        k1:=a[k];
        k2:=b[k];
        repeat
            while (a[i]<k1) or ((a[i]=k1) and (b[i]<k2)) do inc(i);
            while (a[j]>k1) or ((a[j]=k1) and (b[j]>k2)) do dec(j);
            if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    inc(I);
                    dec(j);
                end;
        until i>j;
        if i<r then sort(i,r);
        if l<j then sort(l,j);
    end;
 
procedure lam(u,v:int64);
    var i,j:longint;
    begin
        top3:=0;
        j:=1;
        for i:=1 to top1 do
            begin
                while (j<=top2)and ( p[j]<=q[i]) do
                    begin
                        if p[j]=q[i] then
                            begin
                                inc(top3);
                                st[top3]:=p[j];
                            end;
                        inc(j);
                    end;
            end;
        dem:=dem+int64(top3)*(top3-1) DIV 2;
        if top3>=2 then
        begin
        tg:=int64(st[top3]-st[1])*(v-u);
        if tg=kq1 then inc(kq11);
        if tg>kq1 then
            begin
                kq1:=tg;
                kq11:=1;
            end;
        end;
        for i:=2 to top3 do
            begin
                tg:=int64(st[i]-st[i-1])*(v-u);
                if tg=kq2 then inc(kq22);
                if tg<kq2 then
                    begin
                        kq2:=tg;
                        kq22:=1;
                    end;
            end;
    end;
 
procedure xuli;
    var i,j,k,k1:longint;
    begin
        sort(1,n);
        i:=1;
        a[n+1]:=-maxlongint;
        while i<n do
            begin
                top1:=0;
                for j:=i to n+1 do
                    if a[j]<>a[i] then break
                    else
                        begin
                            inc(top1);
                            q[top1]:=b[j];
                        end;
                if j>n then break;
                k:=j;
                while k<=n do
                    begin
                        top2:=0;
                        for k1:=k to n+1 do
                            if a[k1]<>a[k] then break
                            else
                                begin
                                    inc(top2);
                                    p[top2]:=b[k1];
                                end;
                        lam(a[i],a[k]);
                        k:=k1;
                    end;
                i:=j;
            end;
        writeln(fo,dem);
        if dem>0 then
            begin
                writeln(fo,kq1,' ',kq11);
                writeln(fo,kq2,' ',kq22);
            end;
    end;
 
begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    nhap;
    xuli;
    close(fo);
end.