讨论 / 求解释,爆零了!!
lija 2012-10-08 22:44:00
点我顶贴 收藏 删除
const maxn=100005;

var a,b,f,g:array[0..maxn,1..4] of longint;

n:longint;

procedure qsort(l,r:longint);

var i,j,k,k1:longint;

begin

if l>=r then exit;

i:=l;j:=r;

k:=a[(i+j) div 2,1];

k1:=a[(i+j) div 2,3];

repeat

while (a[i,1]<k)or((a[i,1]=k)and(a[i,3]<k1)) do inc(i);

while (a[j,1]>k)or((a[j,1]=k)and(a[j,3]>k1)) do dec(j);

if i<=j then begin

a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];

inc(i);dec(j);

end;

until i>j;

qsort(i,r);

qsort(l,j);

end;

function min(x,y:longint):longint;

begin

if x<y then exit(x);exit(y);

end;

function max(x,y:longint):longint;

begin

if x>y then exit(x);exit(y);

end;

procedure init;

var i,ans:longint;

begin

readln(n);

for i:=1 to n do

readln(a[i,1],a[i,4],a[i,3],a[i,2]);

qsort(1,n);

f[1]:=a[1];

for i:=2 to n do

begin

if a[i,1]<f[i-1,3] then

begin

if (a[i,2]<f[i-1,4])and(a[i,2]>=f[i-1,2]) then

begin

f[i,1]:=a[i,1];f[i,3]:=min(f[i-1,3],a[i,3]);

f[i,2]:=a[i,2];f[i,4]:=min(f[i-1,4],a[i,4]);

end;

if (a[i,4]<=f[i-1,4])and(a[i,2]>f[i-1,2]) then

begin

f[i,1]:=a[i,1];f[i,3]:=min(f[i-1,3],a[i,3]);

f[i,2]:=max(a[i,2],f[i-1,2]);f[i,4]:=a[i,4];

end;

end

else break;

end;

for i:=1 to n do

b[i]:=a[n-i+1];

g[1]:=b[1];

for i:=2 to n do

begin

if b[i,3]>g[i-1,2] then

begin

if (b[i,4]<=g[i-1,4])and(b[i,4]>g[i-1,2]) then

begin

g[i,1]:=g[i-1,1];g[i,3]:=b[i,3];

g[i,2]:=max(g[i-1,2],b[i,2]);g[i,4]:=b[i,4];

end;

if (b[i,2]>=g[i-1,2])and(b[i,2]<g[i-1,4]) then

begin

g[i,1]:=g[i-1,1];g[i,3]:=b[i,3];

g[i,2]:=b[i,2];g[i,4]:=min(b[i,4],g[i-1,4]);

end;

end

else break;

end;

ans:=(f[n-1,3]-f[n-1,1])*(f[n-1,4]-f[n-1,2]);

if (g[2,3]-g[2,1])*(g[2,4]-g[2,2])>ans then

ans:=(g[2,3]-g[2,1])*(g[2,4]-g[2,2]);

for i:=2 to n-1 do

begin

if g[n-i,1]<f[i-1,3] then

begin

if (g[n-i,2]<f[i-1,4])and(g[n-i,2]>=f[i-1,2]) then

if (f[i-1,3]-g[n-i,1])*(min(f[i-1,4],g[n-i,4])-g[n-i,2])>ans

then ans:=(f[i-1,3]-g[n-i,1])*(min(f[i-1,4],g[n-i,4])-g[n-i,2]);

if (g[n-i,4]<=f[i-1,4])and(g[n-i,4]>f[i-1,2]) then

if (f[i-1,3]-g[n-i,1])*(g[n-i,4]-max(f[i-1,2],g[n-i,2]))>ans

then ans:=(f[i-1,3]-g[n-i,1])*(g[n-i,4]-max(f[i-1,2],g[n-i,2]));

end;

end;

writeln(ans);

end;

begin

init;

end.

查看更多回复
提交回复