Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
线段树水之!!!!!#include <stdio.h> #include <iostream> #include <algorithm> #define M 400+44 using namespace std; struct note { int left; int right; int cover; double len; double ly,ry; }tree[M*4]; struct Line { double x,y1,y2; int flag; }line[M]; double y[M]; bool cmp(Line a,Line b) { return a.x<b.x; } void build(int l,int r,int i) { tree[i].left=l; tree[i].right=r; tree[i].cover=0; tree[i].len=0; tree[i].ly=y[l]; tree[i].ry=y[r]; if(l+1==r) return; int mid=(l+r)>>1; build(l,mid,i<<1); build(mid,r,i<<1|1); }; void update(int i,Line line1) { if(tree[i].ly>=line1.y1&&tree[i].ry<=line1.y2) { tree[i].cover+=line1.flag; if(tree[i].cover>0) { tree[i].len=tree[i].ry-tree[i].ly; } else if(tree[i].left+1==tree[i].right) { tree[i].len=0; } else { tree[i].len=tree[i<<1].len+tree[i<<1|1].len; } return; } if(line1.y1>=tree[i<<1|1].ly) update(i<<1|1,line1); else if(line1.y2<=tree[i<<1].ry) update(i<<1,line1); else { update(i<<1|1,line1); update(i<<1,line1); } if(tree[i].cover==0) tree[i].len=tree[i<<1].len+tree[i<<1|1].len; } int main() { int N; int o=0; while(cin>>N,N) { int t=1,j=1,p=0; for(int i=1;i<=N;i++) { double a,b,c,d; cin>>a>>b>>c>>d; y[j++]=b; y[j++]=d; line[t].flag=1; line[t].x=a; line[t].y1=b; line[t].y2=d; t++; line[t].flag=-1; line[t].x=c; line[t].y1=b; line[t].y2=d; t++; } sort(y+1,y+t); sort(line+1,line+t,cmp); double s=0.0; build (1,t-1,1); update(1,line[1]); for(int i=2;i<t;i++) { s+=tree[1].len*(line[i].x-line[i-1].x); update(1,line[i]); } if(o!=0) printf("\n"); printf("Test case #%d\nTotal explored area: ",++o); printf("%.2f\n",s); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator