poj 1151Atlantis线段树求矩形面积并解题报告

线段树的经典应用，求矩形的面积并，把点的位置离散化，看着别人的代码打出来的，还是没怎么搞懂，看来还是要好好研究研究才好啊，线段树用起来真的太灵活，真的要多练习才好啊。
View Code
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #define l(x) x<<1
  5 #define r(x) x<<1|1
  6 double y[1000];
  7 struct Line
  8 {
  9     double x,y1,y2;
 10     int flag;
 11 }line[300];
 12 struct Node
 13 {
 14     int l,r,cov;
 15     double lf,rf,len;
 16 }node[1000];
 17 int cmp(const void *a,const void *b)
 18 {
 19     Line *c=(Line *)a;
 20     Line *d=(Line *)b;
 21     return 1000*(c->x-d->x);
 22 }
 23 int cmp2(const void *a,const void *b)
 24 {
 25     double c=*(double *)a;
 26     double d=*(double *)b;
 27     return (int)(1000*(c-d));
 28 }
 29 void length(int u)
 30 {
 31     if(node[u].cov>0)
 32     {
 33         node[u].len=node[u].rf-node[u].lf;
 34         return;
 35     }
 36     else if(node[u].l+1==node[u].r)//注意和普通的线段树的不同之处，这里真的成了线段了，有长度，不能在一个点上
 37     {
 38         node[u].len=0;
 39     }
 40     else
 41     node[u].len=node[r(u)].len+node[l(u)].len;
 42 }
 43 void build(int l,int r,int i)
 44 {
 45     node[i].l=l;
 46     node[i].r=r;
 47     node[i].len=node[i].cov=0;
 48     node[i].lf=y[l];
 49     node[i].rf=y[r];
 50     if(l+1==r)
 51     return;
 52     int mid=(l+r)>>1;
 53     build(l,mid,i<<1);
 54     build(mid,r,i<<1|1);
 55 }
 56 void update(int u,Line e)
 57 {
 58     if(e.y1==node[u].lf&&e.y2==node[u].rf)
 59     {
 60         node[u].cov+=e.flag;
 61         length(u);
 62         return;
 63     }
 64     else if(e.y1>=node[r(u)].lf)
 65     update(r(u),e);
 66     else if(e.y2<=node[l(u)].rf)
 67     update(l(u),e);
 68     else
 69     {
 70         Line temp=e;
 71         temp.y2=node[l(u)].rf;
 72         update(l(u),temp);
 73         temp=e;
 74         temp.y1=node[r(u)].lf;
 75         update(r(u),temp);
 76     }
 77     length(u);
 78 }
 79 int main()
 80 {
 81     int n,i,j,icase=1;
 82     int t;
 83     double x1,y1,x2,y2,ans;
 84     while(scanf("%d",&n)&&n)
 85     {
 86         for(i=t=1;i<=n;i++,t++)
 87         {
 88             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 89             line[t].x=x1;
 90             line[t].y1=y1;
 91             line[t].y2=y2;
 92             line[t].flag=1;
 93             y[t]=y1;
 94             t++;
 95             line[t]=line[t-1];
 96             line[t].flag=-1;
 97             line[t].x=x2;
 98             y[t]=y2;
 99         }
100         //printf("%d\n",t);
101         qsort(line+1,t-1,sizeof(Line),cmp);
102         qsort(y+1,t-1,sizeof(double),cmp2);
103         build(1,t-1,1);
104         update(1,line[1]);
105         ans=0;
106         for(i=2;i<t;i++)
107         {
108             ans+=node[1].len*(line[i].x-line[i-1].x);
109             update(1,line[i]);
110         }
111         printf("Test case #%d\n",icase++);
112         printf("Total explored area: %.2lf\n\n",ans);
113     }
114     return 0;
115 }