Atlantis

poj1151:http://poj.org/problem?id=1151

题意：求矩形面积的并
题解：扫描线加线段树

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn=;//注意这里的初始化，不能开小了，是200条边

 int num;//记录x坐标的个数

 struct Node{

     double l;//边的左端点

     double r;//边的又端点

     int tp;//是出度边还是入度边

     double y;//边的纵坐标

  bool operator <(Node a) const{//按照纵坐标给边进行排序，一个比较器

             return y<a.y;

       }

 }line[*maxn];

 double arr[*maxn];//用于离散化

 struct Edge{

     int left;

     int right;

     int flag;//标记该点是加入还是删除

     double sum;

 }node1[maxn*];

 void build(int l,int r,int idx){//建树

     node1[idx].left=l;

     node1[idx].right=r;

     if(l==r){

         node1[idx].flag=;

         node1[idx].sum=;

         return;

     }

     int mid=(l+r)/;

     build(l,mid,idx<<);

     build(mid+,r,idx<<|);

     node1[idx].sum=node1[idx<<].sum+node1[idx<<|].sum;

 }

 void update(int l,int r,int f,int idx){//更新

     if(node1[idx].left==node1[idx].right){

           node1[idx].flag+=f;

         if(node1[idx].flag)node1[idx].sum=arr[node1[idx].right+]-arr[node1[idx].left];//注意这里的家一操作

         if(!node1[idx].flag)node1[idx].sum=;

         return ;

     }

     int mid=(node1[idx].left+node1[idx].right)/;

     if(mid>=r)update(l,r,f,idx<<);

     else if(mid<l)update(l,r,f,idx<<|);

     else{

         update(l,mid,f,idx<<);

         update(mid+,r,f,idx<<|);

     }

     node1[idx].sum=node1[idx<<].sum+node1[idx<<|].sum;//pushup上去

 }

 int binaryserach(double x){//二分查找，也可以写成递归的形是

    int l,r,mid;

       l=,r=num+;

       while (r-l>){

             mid=(l+r)>>;

             if (arr[mid]<=x) l=mid;

                else r=mid;

       }

       return l;

 }

 int main(){

     int n;double x1,y1,x2,y2,ans;

     int t=;

   while(~scanf("%d",&n)&&n){

       num=;

       for(int i=;i<=n;i++){

           scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

           line[*i-].l=x1;line[*i-].r=x2;line[*i-].y=y1;line[*i-].tp=;

           line[*i].l=x1;line[*i].r=x2;line[*i].y=y2;line[*i].tp=-;

           arr[++num]=x1;arr[++num]=x2;//离散化

       }

       sort(arr+,arr+num+);//排序

       n*=;ans=;

       sort(line+,line+n+);

       build(,n,);

      for(int i=;i<=n;i++){

           ans+=node1[].sum*(line[i].y-line[i-].y);

           int l=binaryserach(line[i].l);

           int r=binaryserach(line[i].r)-;//注意这里是要得到区间，不是单个的点，所以要加1

            update(l,r,line[i].tp,);

       }

       printf("Test case #%d\n",t++);

     printf("Total explored area: %.2f\n\n",ans);

   }

 }