Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:线段树+离散化+扫描线

Posted by touhao1234 at 2014-07-30 15:42:34 on Problem 1151
In Reply To:线段树+离散化+扫描线 Posted by:ecjtu_yuweiwei at 2014-07-29 14:58:50
> #include<iostream>
> #include<queue>
> #include<cstdio>]o9ikas
> #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=201;
> using namespace std;
> int sign(double x)
> {
>     return (x>eps)-(x<-eps);
> }
> struct Node
> {
>     int left;
>     int right;//线段树的左右整点
>     int flag;//记录重叠情况,大于零说明没有重叠
>     double cnt;//记录实际的长度
>     double lf;//左边端点真实的浮点数
>     double rf;//右边端点真是的浮点数
> }segTree[Max<<2];
> struct Line
> {
>     double x;
>     double y1;
>     double y2;
>     int ok;
> }line[Max];
> double y[Max];//记录y坐标的数组
> //把一段段平行于y轴的线段表示成数组
> //x是线段的x坐标,y1,y2线段对应的下端点和上端点的坐标
> //一个矩形 ,左边的那条边ok为1,右边的为-1
> //用来记录重叠情况,可以根据node节点中的flag这个来计算
> 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,double x1,double y1,double x2,double 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 n,m,i,j,Case;
>     double x1,y1,x2,y2,area;
>     Case=1;
>     while(cin>>n&&n)
>     {
>         m=1;
>         for(i=1;i<=n;i++)
>         {
>             cin>>x1>>y1>>x2>>y2;
>             Init(m,x1,y1,x2,y2);
>         }
>         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++)
>         {
>             //cout<<segTree[1].cnt<<" "<<line[i-1].x<<" "<<line[i].x<<endl;
>             area+=segTree[1].cnt*(line[i].x-line[i-1].x);
>             Update(1,line[i]);
>         }
>         cout<<"Test case #"<<Case++<<endl;
>         cout<<"Total explored area: "<<setprecision(2)<<setiosflags(ios::fixed)<<area<<endl<<endl;
>     }
>     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator