Atlantis(坐标离散化)

题意：给出矩形的左上角坐标和右下角坐标（坐标的y轴是向下的），求出矩形面积的并。。

今天好困啊。。迷迷糊糊的听会神给讲了讲，敲完之后调试了好久。。原来存错数组了。。看来意识模糊的时候不适宜敲题。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N=550;
 6 
 7 struct node
 8 {
 9     double x1,y1,x2,y2;
10 } p[N];
11 double X[N],Y[N];
12 bool vis[N][N];
13 
14 void init()
15 {
16     memset(vis,0,sizeof(vis));
17     memset(X,0,sizeof(X));
18     memset(Y,0,sizeof(Y));
19 }
20 int BinSearch(double *f,int l,int r,double key)
21 {
22     while(l <= r)
23     {
24         int mid = (l+r)>>1;
25         if (f[mid]==key)
26             return mid;
27         else if (key < f[mid])
28             r = mid-1;
29         else
30             l = mid+1;
31     }
32 }
33 int main()
34 {
35     int o = 0,n;
36     while(~scanf("%d",&n)&&n)
37     {
38         o++;
39         init();
40         int m1=0,m2=0;
41         for (int i = 0; i < n; i++)
42         {
43             scanf("%lf%lf%lf%lf",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
44             X[m1++] = p[i].x1;
45             Y[m2++] = p[i].y1;
46             X[m1++] = p[i].x2;
47             Y[m2++] = p[i].y2;
48         }
49         sort(X,X+m1);
50         sort(Y,Y+m2);
51         for (int i = 0; i < n; i++)
52         {
53             int px1 = BinSearch(X,0,m1-1,p[i].x1);
54             int py1 = BinSearch(Y,0,m2-1,p[i].y1);
55             int px2 = BinSearch(X,0,m1-1,p[i].x2);
56             int py2 = BinSearch(Y,0,m2-1,p[i].y2);
57             for (int i = px1; i < px2; i++)
58             {
59                 for (int j = py1; j < py2; j++)
60                     vis[i][j] = true;
61             }
62 
63         }
64         double area = 0;
65         for (int i = 0; i < m1; i++)
66         {
67             for (int j = 0; j < m2; j++)
68             {
69                 if (vis[i][j])
70                 {
71                     area += (X[i+1]-X[i])*(Y[j+1]-Y[j]);
72                 }
73             }
74         }
75         printf("Test case #%d
",o);
76         printf("Total explored area: %.2f
",area);
77         puts("");
78     }
79     return 0;
80 }

View Code