总的思路是
用线段树维护线段长度
线段长度*h计算面积
具体操作看代码
因为x太大还有离散化一下
学到了好多新姿势
看discuss可能是后台数据有问题 数据要开到1000才能过
1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a)) 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 4 using namespace std; 5 typedef long long ll; 6 7 const int maxn = 1000+10; 8 9 int rm[maxn<<1],col[maxn<<1],add[maxn<<1]; 10 double x[maxn<<1],sum[maxn<<1]; 11 12 struct Line 13 { 14 int kind; 15 double l,r,h;//左端点 右端点 高度 16 Line(){} 17 Line(double x1,double x2,double _h,int d):l(x1),r(x2),h(_h),kind(d){} 18 friend bool operator<(Line p,Line q) 19 { //按照高度排序 20 return p.h<q.h; 21 } 22 }; 23 24 Line line[maxn<<1]; 25 26 void pushup(int l,int r,int rt) 27 { 28 if(col[rt]) 29 {//已经被整段覆盖 30 sum[rt]=x[r+1]-x[l]; 31 } 32 else if(l==r) 33 {//l==r已经不是一条线段 34 sum[rt]=0; 35 } 36 else 37 {//没有被覆盖直接操作左右孩子 38 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 39 } 40 } 41 42 void update(int L,int R,int c,int l,int r,int rt) 43 {//更新线段 44 if(L<=l && r<=R) 45 { 46 col[rt]+=c; 47 pushup(l,r,rt); 48 return ; 49 } 50 int m=l+r>>1; 51 if( L <= m ) update(L,R,c,l,m,rt<<1); 52 if (R > m) update(L,R,c,m+1,r,rt<<1|1); 53 pushup(l,r,rt); 54 } 55 56 int main() 57 { 58 int n,cas=1; 59 while(~scanf("%d",&n)&&n) 60 { 61 int cnt=0; 62 set<double>px; 63 px.clear(); 64 for(int i=0;i<n;i++) 65 { 66 double x1,y1,x2,y2; 67 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 68 px.insert(x1),px.insert(x2);//离散化x轴 69 line[cnt++]=Line(x1,x2,y1,1);//上边 70 line[cnt++]=Line(x1,x2,y2,-1);//下边 71 } 72 sort(line,line+cnt); 73 int cntx=0; 74 for(auto i:px) 75 { 76 x[cntx++]=i; 77 } 78 double ans=0; 79 cl(add,0),cl(sum,0); 80 for(int i=0;i<cnt;i++) //找到每一条线段 并更新 81 { 82 int l=lower_bound(x,x+cntx,line[i].l)-x; 83 int r=lower_bound(x,x+cntx,line[i].r)-x-1; 84 update(l,r,line[i].kind,0,cntx-1,1); 85 ans+=(sum[1]*(line[i+1].h-line[i].h)); 86 } 87 printf("Test case #%d ",cas++); 88 printf("Total explored area: %.2f ",ans); 89 } 90 return 0; 91 }/* 92 93 2 94 10 10 20 20 95 15 15 25 25.5 96 0 97 98 */