学步园

链接：点击打开链接

同样也是求矩形的面积和，线段树+离散化+扫描线，根据hdu 覆盖面积改过来的。不过出现一个问题，用%.2lf不能过，改为%.2f就过啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1100
struct node1{
    double x,y1,y2;
    int flag;
    }a[N];
struct node2{
    double down,up,x;
    int cover,child;
    }anode[N];
double y[N],yd[N];
int m,n;
int cmp(node1 a,node1 b){
    return a.x<b.x;
    }
void bulid(int l,int r,int n){
    anode[n].down=yd[l];
    anode[n].up=yd[r];
    anode[n].child=1;
    anode[n].cover=0;
    if(l==r-1){
        anode[n].child=0;
        return;
        }
    int mid=(l+r)>>1;
    bulid(l,mid,2*n);
    bulid(mid,r,2*n+1);    
    }    
double update(double l,double r,double x,int flag,int n){
    if(anode[n].up <= l || anode[n].down >= r)
  return 0;
 if(anode[n].child == 0)
 {
  if(anode[n].cover > 0)
  {
   double ans = (x-anode[n].x)*(anode[n].up-anode[n].down);
   anode[n].cover += flag;
   anode[n].x = x;
   return ans;
  }
  else
  {
   anode[n].cover += flag;
   anode[n].x = x;
   return 0;
  }
 }
 return update(l,r,x,flag,2*n)+update(l,r,x,flag,2*n+1);
    }    
int    main(){
    int i,j,t=1;
    double x1,y1,x2,y2,aera;
    while(~scanf("%d",&n)){
        m=0;
        if(n==0)
        break;
        for(i=1;i<=n;i++){
            scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
            m++;
            a[m].x=x1,a[m].y1=y1,a[m].y2=y2,a[m].flag=1;
            y[m]=y1;
            m++;
            a[m].x=x2,a[m].y1=y1,a[m].y2=y2,a[m].flag=-1;
            y[m]=y2;
            }
            sort(y+1,y+1+m);
            sort(a+1,a+1+m,cmp);
            j=1;
            yd[1]=y[1];
            for(i=2;i<=m;i++){
                if(y[i]!=y[i-1])
                yd[++j]=y[i];
                }
            bulid(1,j,1);
             aera=0;
            for(i=1;i<=m;i++)
                aera+=update(a[i].y1,a[i].y2,a[i].x,a[i].flag,1);
                printf("Test case #%d\n",t++);
                printf("Total explored area: %.2f\n\n",aera);    
        }
      return 0;
    }