数据范围较小，直接离散后暴力。等等学习一下线段树的思路。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define N 101 7 #define eps 1e-6 8 double xr[N],xc[N],yr[N],yc[N]; 9 double x[3*N],y[3*N];10 int dblcmp(double x)11 {12 if(fabs(x) < eps)13 return 0;14 return x > 0 ? 1:-1;15 }16 int main()17 {18 int n,r,c,i,j,k,cas = 1;19 double ans;20 while(scanf("%d",&n)!=EOF)21 {22 if(!n) break;23 ans = 0;24 for(i = 0; i < n; i ++)25 {26 scanf("%lf%lf%lf%lf",&xr[i],&yr[i],&xc[i],&yc[i]);27 x[2*i] = xr[i];28 x[2*i+1] = xc[i];29 y[2*i] = yr[i];30 y[2*i+1] = yc[i];31 }32 r = c = 0;33 sort(x,x+2*n);34 sort(y,y+2*n);35 for(i = 1;i < 2*n;i ++)36 {37 if(dblcmp(x[i]-x[r]) == 0)38 continue;39 x[++r] = x[i];40 }41 for(i = 1;i < 2*n;i ++)42 {43 if(dblcmp(y[i]-y[c]) == 0)44 continue;45 y[++c] = y[i];46 }47 for(i = 0;i < r;i ++)48 {49 for(j = 0;j < c;j ++)50 {51 for(k = 0;k < n;k ++)52 {53 if(dblcmp(x[i]-xr[k])>=0&&dblcmp(y[j]-yr[k])>=0&&dblcmp(x[i+1]-xc[k])<=0&&dblcmp(y[j+1]-yc[k])<=0)54 break;55 }56 if(k != n) ans += (x[i+1]-x[i])*(y[j+1]-y[j]);57 }58 }59 printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++,ans);60 }61 return 0;62 }
线段树版本主要是看的以下的博客。
后一个博客的图很不错。HH解释很好，就是把矩形分为上边和下边，从下到上，扫描。cnt记录区间下边比上边多几条，sum记录存在的长度。一段一段的更新，然后计算即可。
2013-06-20
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define maxn 5000 7 #define lson l , m, rt<<1 8 #define rson m+1, r,rt<<1|1 9 double que[maxn]; 10 double sum[maxn]; 11 int cnt[maxn]; 12 struct node 13 { 14 double lx,rx,y; 15 int s; 16 node(){} 17 node(double a,double b,double c,int d):lx(a),rx(b),y(c),s(d){} 18 bool operator < (const node &S) const 19 { 20 return y < S.y; 21 } 22 }mat[maxn]; 23 int bin(double x,int n) 24 { 25 int str,end,mid; 26 str = 0,end = n; 27 while(str <= end) 28 { 29 mid = (str+end)/2; 30 if(que[mid] == x) 31 return mid; 32 else if(que[mid] > x) 33 end = mid - 1; 34 else 35 str = mid + 1; 36 } 37 return mid; 38 } 39 void pushup(int rt,int l,int r) 40 { 41 if(cnt[rt]) 42 sum[rt] = que[r+1] - que[l]; 43 else if(l == r) 44 sum[rt] = 0; 45 else 46 sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 47 } 48 void update(int L,int R,int c,int l,int r,int rt) 49 { 50 if(L <= l&&r <= R) 51 { 52 cnt[rt] += c; 53 pushup(rt,l,r); 54 return ; 55 } 56 int m = (l+r)>>1; 57 if(L <= m) 58 update(L,R,c,lson); 59 if(R > m) 60 update(L,R,c,rson); 61 pushup(rt,l,r); 62 } 63 int main() 64 { 65 int n,num,i,l,r,cas = 1; 66 double a,b,c,d; 67 while(scanf("%d",&n)!=EOF) 68 { 69 if(!n) break; 70 num = 0; 71 for(i = 0;i < n;i ++) 72 { 73 scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 74 que[num] = a; 75 mat[num ++] = node(a,c,b,1); 76 que[num] = c; 77 mat[num ++] = node(a,c,d,-1); 78 } 79 sort(que,que+num); 80 sort(mat,mat+num); 81 int k = 1; 82 for(i = 1;i < num;i ++) 83 { 84 if(que[i] != que[i-1]) 85 que[k++] = que[i]; 86 } 87 double ans = 0; 88 memset(cnt,0,sizeof(cnt)); 89 memset(sum,0,sizeof(sum)); 90 for(i = 0;i < num-1;i ++) 91 { 92 l = bin(mat[i].lx,k-1); 93 r = bin(mat[i].rx,k-1) - 1; 94 if(l <= r) 95 update(l,r,mat[i].s,0,k-1,1); 96 ans += (mat[i+1].y - mat[i].y)*sum[1]; 97 } 98 printf("Test case #%d\nTotal explored area: %.2f\n\n",cas++,ans); 99 }100 return 0;101 }