讨论 / 九月月赛ract,请大牛更正思路
谧芒 2012-10-09 01:47:00
点我顶贴 收藏 删除
九月月赛ract,我的思路是所有的矩形只要有交集,就一定是个矩形,我在读入的时候

进行处理,求出了最中心的小矩形也就是所有矩形的交集,记录个边所在的矩形,同时记录了各边的最近的边(删除时求面积用)然后枚举删除这四个矩形求出最大值,这是我的代码,如果我错了,希望能得到更正!!!

program aa;

var

a:array[1..100000] of record

x1,x2,y1,y2:longint;

end;

maxl,maxr,maxh,maxd:longint;最小矩形边

maxl_1,maxr_1,maxh_1,maxd_1:longint;最小矩形边的临边

x,y,xx,yy:longint;

n,i:longint;

max,t:int64;

function del(x:longint):int64;//枚举删除第X个矩形

var

l,r,d,h:longint;

begin

l:=maxl;

r:=maxr;

d:=maxd;

h:=maxh;

if a[x].x1=maxl then l:=maxl_1;

if a[x].x2=maxr then r:=maxr_1;

if a[x].y2=maxh then h:=maxh_1;

if a[x].y1=maxd then d:=maxd_1;

exit((r-l)*(h-d));

end;

begin

assign(input,'f:\aa.txt');reset(input);

readln(n);

maxl:=-1000;maxl_1:=-1000;

maxd:=-1000;maxd_1:=-1000;

maxr:= 1000;maxr_1:= 1000;

maxh:= 1000;maxh_1:= 1000;

for i:=1 to n do

begin

readln(a[i].x1,a[i].y1,a[i].x2,a[i].y2);

if a[i].x1>maxl then begin maxl_1:=maxl; maxl:=a[i].x1;x:=i;end

else if a[i].x1>maxl_1 then maxl_1:=a[i].x1;

if a[i].x2<maxr then begin maxr_1:=maxr;maxr:=a[i].x2;y:=i;end

else if a[i].x2<maxr_1 then maxr_1:=a[i].x2;

if a[i].y1>maxd then begin maxd_1:=maxd;maxd:=a[i].y1;xx:=i;end

else if a[i].y1>maxd_1 then maxd_1:=a[i].y1;

if a[i].y2<maxh then begin maxh_1:=maxh;maxh:=a[i].y2;yy:=i;end

else if a[i].y2<maxh_1 then maxh_1:=a[i].y2;

end;

max:=0;

t:=del(x);

if t>max then max:=t;

t:=del(y);

if t>max then max:=t;

t:=del(xx);

if t>max then max:=t;

t:=del(yy);

if t>max then max:=yy;

writeln(max);

end.

这几组数都过了,我自己做的

6

1 0 5 4

2 1 6 5

3 1 5 4

3 1 6 4

3 1 5 4

3 1 4 3

5

5

1 0 5 4

2 1 6 5

3 1 5 4

3 1 4 3

3 1 6 4

希望大牛帮忙!!

#1 大江西@2012-10-08 06:28:00
回复 删除
如果全部矩形没有交集,上述算法就不能实现了

但n-1个矩形的最大交集是存在的

其实这道题是USACO上一道题的加强版

#2 谧芒@2012-10-09 01:47:00
回复 删除
感谢指导

我再试试,初赛了,放一放

查看更多回复
提交回复