一道离散化+线段树+扫描线的题

这道题感觉快哭了卡了一个差不多礼拜然后发现输出用%.2lf是过不了的必须用%.2f才能过这是一道好（lan）题；
%f 一般对应单精度类型 float
%lf 一般对应双精度类型 double
  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cmath>
  4 #include<set>
  5 #include<cstdio>
  6 
  7 using namespace std;
  8 
  9 double y[210];
 10 typedef struct _NODE_
 11 {
 12     int L,R;
 13     _NODE_ *PLeft,*PRight;
 14     double Len;   //当前,本区间上有多长的部分是落在那些矩形中的
 15     int Covers;   //本区间当前被多少个矩形完全包含
 16 }NODE;
 17 
 18 NODE Tree[10000];
 19 
 20 typedef struct _LINE_
 21 {
 22     double x,y,y1,y2;
 23     bool bLeft;      //是否是矩形的左边
 24 }LINE;
 25 
 26 LINE Line[210];
 27 
 28 int iNodeCount = 0;
 29 bool operator < (const LINE& l1,const LINE& l2)
 30 {
 31     return l1.x < l2.x;
 32 }
 33 template<class F,class T>
 34 F bin_search(F s,F e,T val)
 35 {
 36     F  L = s;
 37     F  R = e-1;
 38     while (L<=R)
 39     {
 40         F mid = L+(R-L)/2;
 41         if (!(*mid<val||val<*mid))
 42         {
 43             return mid;
 44         }
 45         else if (val<*mid)
 46         {
 47             R = mid-1;
 48         }
 49         else 
 50         {
 51             L = mid+1;
 52         }
 53     }
 54     return e;
 55 }
 56 int Mid(NODE* PRoot)
 57 {
 58     return (PRoot->L+PRoot->R)>>1;
 59 }
 60 void Insert(NODE* PRoot,int L,int R)
 61 {
 62     if (PRoot->L==L&&PRoot->R==R)
 63     {
 64         PRoot->Len = y[R+1]-y[L];
 65         PRoot->Covers++;
 66         return ;
 67     }
 68     if (R <= Mid(PRoot))
 69     {
 70         Insert(PRoot->PLeft,L,R);
 71     }
 72     else if (L>=Mid(PRoot)+1)
 73     {
 74         Insert(PRoot->PRight,L,R);
 75     }
 76     else 
 77     {
 78         Insert(PRoot->PLeft,L,Mid(PRoot));
 79         Insert(PRoot->PRight,Mid(PRoot)+1,R);
 80     }
 81     if (PRoot->Covers==0) //如果不为0，则说明本区间当前仍然被某个矩形完全包含，则不能更新 Len
 82     {
 83         PRoot->Len = PRoot->PLeft->Len + PRoot->PRight->Len;
 84     }
 85 }
 86 
 87 
 88 void Delete(NODE* PRoot,int L,int R) //在区间pRoot 删除矩形右边的一部分或全部，该矩形右边的一部分或全部覆盖了区间[L,R]
 89 {
 90     if (PRoot->L==L&&PRoot->R==R)
 91     {
 92         PRoot->Covers--;
 93         if (PRoot->Covers==0)
 94         {
 95             if (PRoot->L==PRoot->R)
 96             {
 97                 PRoot->Len = 0;
 98             }
 99             else 
100             {
101                 PRoot->Len = PRoot->PLeft->Len+PRoot->PRight->Len;
102             }
103         }
104         return ; 
105     }
106     if (R<=Mid(PRoot))
107     {
108         Delete(PRoot->PLeft,L,R);
109     }
110     else if (L>=Mid(PRoot)+1)
111     {
112         Delete(PRoot->PRight,L,R);
113     }
114     else 
115     {
116         Delete(PRoot,L,Mid(PRoot));
117         Delete(PRoot->PRight,Mid(PRoot)+1,R);
118     }
119     if (PRoot->Covers==0) //如果不为0，则说明本区间当前仍然被某个矩形完全包含，则不能更新 Len
120     {
121         PRoot->Len = PRoot->PLeft->Len+PRoot->PRight->Len;
122     }
123 }
124 
125 void BuildTree(NODE* PRoot,int L,int R)
126 {
127     PRoot->L = L;
128     PRoot->R = R;
129     PRoot->Covers = 0;
130     PRoot->Len = 0;
131     if (L == R)
132     return ;
133     iNodeCount++;
134     PRoot->PLeft = Tree + iNodeCount;
135     iNodeCount++;
136     PRoot->PRight = Tree+ iNodeCount;
137     BuildTree(PRoot->PLeft,L,(L+R)/2);
138     BuildTree(PRoot->PRight,(L+R)/2+1,R);
139 }
140 
141 
142 void work()
143 {
144     int i,j,k,n;
145     double x1,x2,y1,y2;
146     int yc,lc;
147     int iCount = 0;
148     int t = 0;
149     
150 //yc 是横线的条数，yc- 1是纵向区间的个数，这些区间从0
151 //开始编号，那么最后一个区间
152 //编号就是yc - 1 -1
153     while (~scanf("%d",&n)&&n)
154     {
155         t++; yc = lc = 0;
156         for (i = 0;i<n;i++)
157         {
158             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
159             y[yc++] = y1;  y[yc++] = y2;
160             Line[lc].x = x1; Line[lc].y1 = y1;
161             Line[lc].y2 = y2; Line[lc].bLeft = true;
162             lc++;
163             Line[lc].x = x2;  Line[lc].y1 = y1;
164             Line[lc].y2 = y2; Line[lc].bLeft = false;
165             lc++;
166         }
167         sort(y,y+yc);
168         yc = unique(y,y+yc)-y;
169         iNodeCount = 0;
170         BuildTree(Tree,0,yc-1-1);
171         sort(Line,Line+lc);
172         double Area = 0;
173         for (i = 0;i<lc-1;i++)
174         {
175             int L = bin_search(y,y+yc,Line[i].y1)-y;
176             int R = bin_search(y,y+yc,Line[i].y2)-y;
177             if (Line[i].bLeft)
178             {
179                 Insert(Tree,L,R-1);
180             }
181             else 
182             {
183                 Delete(Tree,L,R-1);
184             }
185             Area += Tree[0].Len*(Line[i+1].x-Line[i].x);
186         }
187         printf("Test case #%d
",t);
188         printf("Total explored area: %.2f
",Area);
189         printf("
");
190     }
191     return ;
192 }
193 
194 int main()
195 {
196     work();
197     return 0;
198 }
代码大哥
爱程序不爱bug 爱生活不爱黑眼圈我和你们一样我和你们不一样我不是凡客我要做geek