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

线段树+离散化+扫描线水之~~

Posted by ecjtu_yuweiwei at 2014-07-30 16:29:09 on Problem 1389
#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:
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