Đề 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. |
Speak Your Mind