rect

题目描述

给定N个矩形。请删掉一个，使得其余n-1个矩形的公共部分（即这n-1个矩形的交）的面积最大。

对于30%：N <= 100, 所有的坐标的绝对值 <= 200
对于60%：N <= 1000
对于100%：N <= 100000，所有的坐标的绝对值 <= 10^9

时限：1s
内存限制：256MB

输入格式

第一行一个整数N，表示矩形的个数
接下来N行每行四个整数x1, y1, x2, y2，表示这个矩形左上角、右下角的坐标。

输出格式

一个整数表示最大的公共部分面积。
如需输出64位整数，请使用cout或者printf("%I64d")。

long long 参数 scanf 什么的害死人

head[i]表示前i个矩形重叠坐标。
tail[i]表示后i 个矩形重叠坐标。
然后枚举拿掉的矩形。

 1 head[i]表示前i个矩形重叠坐标。
 2 tail[i]表示后i 个矩形重叠坐标。
 3 然后枚举拿掉的矩形。
 4 
 5 #include<iostream>
 6 #include<stdio.h>
 7 using namespace std;
 8 
 9 long long n,k;
10 long long ans=0;
11 struct{long long x1,y1,x2,y2;}node[100005],head[100005],tail[100005];
12 long long x1,y1,x2,y2;
13 
14 void Dfs(){
15      if(k==n) return ;
16      if(node[k+1].x1>=x2||node[k+1].y1>=y2||node[k+1].x2<=x1||node[k+1].y2<=y1) return ;
17      x1=max(x1,node[k+1].x1);y1=max(y1,node[k+1].y1);x2=min(x2,node[k+1].x2);y2=min(y2,node[k+1].y2);
18      head[k+1].x1=x1;head[k+1].y1=y1;
19      head[k+1].x2=x2;head[k+1].y2=y2;
20      k++;
21      Dfs();
22      }
23 
24 void Dfs2(){
25      if(k==1) return ;
26      if(node[k-1].x1>=x2||node[k-1].y1>=y2||node[k-1].x2<=x1||node[k-1].y2<=y1) return ;
27      x1=max(x1,node[k-1].x1);y1=max(y1,node[k-1].y1);x2=min(x2,node[k-1].x2);y2=min(y2,node[k-1].y2);
28      tail[k-1].x1=x1;tail[k-1].y1=y1;
29      tail[k-1].x2=x2;tail[k-1].y2=y2;
30      k--;
31      Dfs2();
32      }
33 
34 int main()
35 {
36     scanf("%I64d",&n);
37     for(int i=1;i<=n;++i)
38     scanf("%I64d%I64d%I64d%I64d",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);
39     
40     for(int i=1;i<=n;++i)
41     head[i].x1=head[i].y1=head[i].x2=head[i].y2=0;
42     head[1].x1=x1=node[1].x1;head[1].y1=y1=node[1].y1;
43     head[1].x2=x2=node[1].x2;head[1].y2=y2=node[1].y2;
44     k=1;
45     Dfs();
46     
47     for(int i=1;i<=n;++i)
48     tail[i].x1=tail[i].y1=tail[i].x2=tail[i].y2=0;
49     tail[n].x1=x1=node[n].x1;tail[n].y1=y1=node[n].y1;
50     tail[n].x2=x2=node[n].x2;tail[n].y2=y2=node[n].y2;
51     k=n;
52     Dfs2();
53     
54     x1=tail[2].x1;y1=tail[2].y1;
55     x2=tail[2].x2;y2=tail[2].y2;
56     if(ans<(y2-y1)*(x2-x1)) ans=(y2-y1)*(x2-x1);
57     
58     x1=head[n-1].x1;y1=head[n-1].y1;
59     x2=head[n-1].x2;y2=head[n-1].y2;
60     if(ans<(y2-y1)*(x2-x1)) ans=(y2-y1)*(x2-x1);
61     
62     for(int i=2;i<=n-1;++i)
63     {
64       if(head[i-1].x1>=tail[i+1].x2||head[i-1].y1>=tail[i+1].y2||head[i-1].x2<=tail[i+1].x1||head[i-1].y2<=tail[i+1].y1)
65       continue ;   //为什么不能用break?
66       
67       x1=max(head[i-1].x1,tail[i+1].x1);
68       y1=max(head[i-1].y1,tail[i+1].y1);
69       x2=min(head[i-1].x2,tail[i+1].x2);
70       y2=min(head[i-1].y2,tail[i+1].y2);
71       
72       if(ans<(y2-y1)*(x2-x1)) ans=(y2-y1)*(x2-x1);
73             }
74     
75     cout<<ans<<endl;
76    // system("pause");
77     return 0;
78     
79     }