POJ1151 离散化求矩形面积的并

 1 /*第一道离散化的题目，虽然是水题，不过还是很高兴。。。*/
 2 
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 struct rect
 8 {
 9  double x1,x2,y1,y2;
10 };
11 #define max 103<<1
12 rect a[max>>1];
13 double x[max],y[max];
14 bool flag[max][max];
15 int n;
16 double sum;
17 
18 void solve()
19 {
20  for(int i=0;i<n;i++)
21  {
22   for(int j=0;j<n<<1;j++)
23   {
24    if(x[j]>=a[i].x2)
25     break;
26    if(x[j]<a[i].x1)
27     continue;
28    for(int k=0;k<n<<1;k++)
29    {
30     if(y[k]>=a[i].y2)
31      break;
32     if(y[k]<a[i].y1)
33      continue;
34     flag[j][k]=true;
35    }
36   }
37  }
38  for(int i=0;i<n<<1;i++)
39   for(int j=0;j<n<<1;j++)
40   {
41    if(flag[i][j])
42     sum+=(x[i+1]-x[i])*(y[j+1]-y[j]);
43   }
44 }
45 
46 int main()
47 {
48  int k=1;
49  while(~scanf("%d",&n)&&n)
50  {
51   int cnt=0;
52   for(int i=0;i<n;i++)
53   {
54    scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
55    x[cnt]=a[i].x1;y[cnt]=a[i].y1;cnt++;
56    x[cnt]=a[i].x2;y[cnt]=a[i].y2;cnt++;
57   }
58   sort(x,x+cnt);
59   sort(y,y+cnt);
60   sum=0;
61   memset(flag,false,sizeof(flag));
62   solve();
63   printf("Test case #%d
",k++);
64   printf("Total explored area: %.2lf

",sum);
65  }
66 }
67