hdu1542线段树+离散化+扫描线

时间：2023-03-08 21:47:17

参考博客：

http://blog.****.net/xingyeyongheng/article/details/8927732

总的来说就是用一条(假想的）线段去平行x轴从下往上扫描，扫描的过程中更新下底边的个数和长度综合（用线段树维护）

因为x的值可能会很大，所以就要用Hash表来进行离散化，排序，去重，查找的时候直接二分就好了

二分搜索传参数的时候double写成了int交上去居然是mle（想不通为什么）

注释都在代码里面了

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

int mark[N<<];//某区间下底边个数

double sum[N<<];//某区间下底边总长度

double Hash[N];//离散化数组

//把横坐标作为线段进行扫描

//扫描是为了更新下底边个数和下底边总长度，记录答案

struct tree{

    double l,r,h;//l,r左右端点,h从x轴到该边的高

    int d;//-1上底边/1下底边

    tree(){}

    tree(double x,double y,double z,int a):l(x),r(y),h(z),d(a){}

    bool operator <(const tree &a)const

    {

        return h<a.h;

    }

}s[N];

void pushup(int l,int r,int rt)

{

    if(mark[rt])sum[rt]=Hash[r+]-Hash[l];

    else if(l==r)sum[rt]=;

    else sum[rt]=sum[rt<<]+sum[rt<<|];

}

void update(int L,int R,int d,int l,int r,int rt)

{

    if(L<=l&&r<=R)

    {

        mark[rt]+=d;//如果是上底边mark-1，下底边mark+1

        pushup(l,r,rt);

        return ;

    }

    int m=(l+r)>>;

    if(L<=m)update(L,R,d,ls);

    if(R>m)update(L,R,d,rs);

    pushup(l,r,rt);

}

int Search(double key,int n)

{

    int l=,r=n-;

    while(l<=r)

    {

        int m=(l+r)/;

        if(Hash[m]==key)return m;

        if(Hash[m]>key)r=m-;

        else l=m+;

    }

    return -;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cout<<setiosflags(ios::fixed)<<setprecision();

    int n,cnt=;

    while(cin>>n,n)

    {

        int k=;

        for(int i=;i<n;i++)

        {

            double x1,x2,y1,y2;

            cin>>x1>>y1>>x2>>y2;

            Hash[k]=x1;

            s[k++]={x1,x2,y1,};//上底边

            Hash[k]=x2;

            s[k++]={x1,x2,y2,-};//下底边

        }

        sort(Hash,Hash+k);

        sort(s,s+k);

        int m=;

        for(int i=;i<k;i++)//离散化

            if(Hash[i]!=Hash[i-])

                Hash[m++]=Hash[i];

        double ans=;

        memset(sum,,sizeof sum);

        memset(mark,,sizeof mark);

        for(int i=;i<k;i++)//如果两个下底边重合，但是上底边可能不一样，必须更新mark，而sum不会改变

        {

            int l=Search(s[i].l,m);//利用hash表查找

            int r=Search(s[i].r,m)-;//这里的l，r实际上是Hash表的标号

            update(l,r,s[i].d,,m-,);//维护mark和sum的值

            ans+=sum[]*(s[i+].h-s[i].h);//sum[1]当前的下底边长度总和

        }

        cout<<"Test case #"<<++cnt<<endl;

        cout<<"Total explored area: "<<ans<<endl<<endl;

    }

    return ;

}

/*********************

*********************/

相关文章