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<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<iomanip> #include<map> #include<cstdlib> #include<cmath> #include<vector> #define LL long long #define IT __int64 #define zero(x) fabs(x)<eps #define mm(a,b) memset(a,b,sizeof(a)) const int INF=0x7fffffff; const double inf=1e8; const double eps=1e-10; const double PI=acos(-1.0); const int Max=20000; using namespace std; int sign(double x) { return (x>eps)-(x<-eps); } struct Node { int left; int right;//线段树的左右整点 int flag;//记录重叠情况,大于零说明没有重叠 int cnt;//记录实际的长度 int lf;//左边端点真实的浮点数 int rf;//右边端点真是的浮点数 }segTree[Max]; struct Line { int x; int y1; int y2; int ok; }line[Max]; int y[Max];//记录y坐标的数组 bool cmp(Line u,Line v)//sort排序 { return u.x<v.x; } void Build_Tree(int t,int left,int right) { segTree[t].left=left; segTree[t].right=right; segTree[t].lf=y[left]; segTree[t].rf=y[right]; if((left+1)==right) return; int mid=(left+right)>>1; Build_Tree(t<<1,left,mid); Build_Tree(t<<1|1,mid,right);//递归构造线段树,这里mid不能+1因为如果+1那么t<<1的右孩子和t<<1|1的左孩子不能产生联系最终更新父节点就是错误的数据 } void Calen(int t)//计算长度 { if(segTree[t].flag>0)//如果没有重叠 { segTree[t].cnt=segTree[t].rf-segTree[t].lf; } else if(segTree[t].left+1==segTree[t].right)//如果重叠了 { segTree[t].cnt=0; } else { segTree[t].cnt=segTree[t<<1].cnt+segTree[t<<1|1].cnt; } } void Update(int t,Line L)//加入线段L,后更新线段树 { if(L.y1==segTree[t].lf&&L.y2==segTree[t].rf) { segTree[t].flag+=L.ok; Calen(t); } else if(L.y2<=segTree[t<<1].rf) { Update(t<<1,L); } else if(L.y1>=segTree[t<<1|1].lf) { Update(t<<1|1,L); } else { Line temp; temp=L; temp.y2=segTree[t<<1].rf; Update(t<<1,temp); temp=L; temp.y1=segTree[t<<1|1].lf; Update(t<<1|1,temp); } Calen(t); } void Init(int &m,int x1,int y1,int x2,int y2) { line[m].x=x1; line[m].y1=y1; line[m].y2=y2; line[m].ok=1; y[m]=y1; m++; line[m].x=x2; line[m].y1=y1; line[m].y2=y2; line[m].ok=-1; y[m]=y2; m++; } int main() { int m,i,j,p; int x1,y1,x2,y2,area; p=0; m=1; while(cin>>x1>>y1>>x2>>y2) { if(x1==-1&&y1==-1&&x2==-1&&y2==-1) p+=1; else p=0; if(p==1) { sort(line+1,line+m,cmp); sort(y+1,y+m); Build_Tree(1,1,m-1); Update(1,line[1]); area=0; for(i=2;i<m;i++) { area+=segTree[1].cnt*(line[i].x-line[i-1].x); Update(1,line[i]); } cout<<area<<endl; m=1; } if(p==2) break; Init(m,x1,y1,x2,y2); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator