선분 트 리 앨범 - hdu 1255 커버 면적

  1 #include<iostream>
  2 #include<string>
  3 #include<stdlib.h>
  4 using namespace std;
  5 
  6 typedef struct
  7 {
  8     double x;
  9     double y_up;
 10     double y_down;
 11     int l_r;
 12 }LINE;
 13 
 14 typedef struct
 15 {
 16     double x;
 17     double y_up;
 18     double y_down;
 19     int cover;
 20     bool has_child;
 21 }TREE;
 22 
 23 int cmp(const void *a,const void *b)
 24 {
 25     return *(double *)a>*(double *)b? 1: -1;
 26 }
 27 
 28 TREE tree[1000*1001];
 29 LINE line[2002];
 30 int n,index;
 31 double x1,y1,x2,y2;
 32 double y[2002];
 33 
 34 void build(int i,int l,int r)
 35 {
 36     tree[i].cover=0;
 37     tree[i].x=-1;
 38     tree[i].has_child=true;
 39     tree[i].y_up=y[r];
 40     tree[i].y_down=y[l];
 41     if(l+1==r)
 42     {
 43         tree[i].has_child=false;
 44         return;
 45     }
 46     int mid=(l+r)>>1;
 47     build(2*i,l,mid);
 48     build(2*i+1,mid,r);
 49 }
 50 
 51 double insert(int i,double l,double r,double x,int l_r)
 52 {
 53     if(tree[i].y_up<=l || tree[i].y_down>=r)
 54         return 0;
 55     if(!tree[i].has_child)
 56     {
 57         if(tree[i].cover>1)
 58         {
 59             double ans=(x-tree[i].x)*(tree[i].y_up-tree[i].y_down);
 60             tree[i].x=x;
 61             tree[i].cover+=l_r;
 62             return ans;
 63         }
 64         else
 65         {
 66             tree[i].cover+=l_r;
 67             tree[i].x=x;
 68             return 0;
 69         }
 70     }
 71     else
 72         return insert(2*i,l,r,x,l_r)+insert(2*i+1,l,r,x,l_r);
 73 }
 74 
 75 int main()
 76 {
 77     int t,i;
 78     //freopen("D:\\in.txt","r",stdin);
 79     cin>>t;
 80     while(t--)
 81     {
 82         cin>>n;
 83         index=1;
 84         for(i=1;i<=n;i++)
 85         {
 86             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 
 87             line[index].x=x1;
 88             line[index].l_r=1;
 89             line[index].y_up=y2;
 90             line[index].y_down=y1;
 91             y[index]=y1;
 92             index++;
 93 
 94             line[index].x=x2;
 95             line[index].l_r=-1;
 96             line[index].y_up=y2;
 97             line[index].y_down=y1;
 98             y[index]=y2;
 99             index++;
100         }
101         qsort(y+1,2*n,sizeof(y[0]),cmp);
102         qsort(line+1,2*n,sizeof(line[0]),cmp);
103         build(1,1,index-1);
104         double ans=0;
105         for(i=1;i<index;i++)
106         {
107             ans+=insert(1,line[i].y_down,line[i].y_up,line[i].x,line[i].l_r);
108         }
109         printf("%.2lf
",ans);
110     }
111     return 0;
112 }