HDU - 1542 Atlantis（线段树求面积并）

时间：2021-05-23 14:29:40

https://cn.vjudge.net/problem/HDU-1542

题意

求矩形的面积并

分析

点为浮点数，需要离散化处理。

给定一个矩形的左下角坐标和右上角坐标分别为:(x1,y1)、(x2,y2)，对这样的一个矩形，我们构造两条线段，一条定位在x1，它在y坐标的区间是[y1,y2]，并且给定一个cover域值为1；另一条线段定位在x2，区间一样是[y1,y2]，给定它一个cover值为-1。根据这样的方法对每个矩形都构造两个线段，最后将所有的线段根据所定位的x从左到右进行排序。插入某跟线段的时候，只要看该线段所在区间上的cover是否大于等于1，如果是，那么就可以将并面积值加上(目前线段的x定位 - 上一线段的x定位)*（该区间的大小）。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define eps 0.0000000001

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

const int maxm =  + ;

const int mod = ;

int n;

double y[maxn];

struct LINE{

    double x;

    double y1,y2;

    int flag;

    bool operator <(const LINE &a)const{

        return x<a.x;

    }

}line[maxn];

struct ND{

    double l,r;

    double x;

    int cover;

    bool flag;

}tree[maxn<<];

void build(int rt,int l,int r){

    tree[rt].l=y[l];

    tree[rt].r=y[r];

    tree[rt].x=-;

    tree[rt].flag=false;

    tree[rt].cover=; //表示该区间有多少线段，左加右减

    if(l+==r){//叶结点

        tree[rt].flag=true;

        return;

    }

    int mid = (l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid,r);//这里是mid

}

double insert_query(int rt,double x,double l,double r,int flag){

    if(l>=tree[rt].r||r<=tree[rt].l) return ; //检验区间合法

    if(tree[rt].flag){

        if(tree[rt].cover>){

            double ans=(x-tree[rt].x)*(tree[rt].r-tree[rt].l);

            tree[rt].x=x;

            tree[rt].cover+=flag;

            return ans;

        }else{

            tree[rt].x=x;

            tree[rt].cover+=flag;

            return ;

        }

    }

    return insert_query(rt<<,x,l,r,flag)+insert_query(rt<<|,x,l,r,flag);

}

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    int T,cas=;

//    scanf("%d",&T);

    while(~scanf("%d",&n)&&n){

        int cnt=-;

        double x1,x2,y1,y2;

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

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            y[++cnt]=y1;

            line[cnt].x=x1;

            line[cnt].y1=y1;

            line[cnt].y2=y2;

            line[cnt].flag=;//左边

            y[++cnt]=y2;

            line[cnt].x=x2;

            line[cnt].y1=y1;

            line[cnt].y2=y2;

            line[cnt].flag=-;//右边

        }

        sort(y,y++cnt);

        sort(line,line++cnt);

        build(,,cnt);

        double area=;

        for(int i=;i<=cnt;i++){

            area+=insert_query(,line[i].x,line[i].y1,line[i].y2,line[i].flag);

        }

        printf("Test case #%d\nTotal explored area: %.2f\n\n",cas++,area);

    }

    return ;

}

还有一种高端做法。

该方法同样需要在线段树中定义一个cover域，表示该线段区间目前被覆盖的线段数目。另外再加一个len域，表示该区间可用于与下一线段求并面积的y坐标区间长度。然后利用简单的dp，将所有信息集中于tree[1].len上，这样便不用想第一种方法那样每次都求到叶子线段，大大节约了时间，并且代码也少了很多。

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

struct node

{

    int l;

    int r;

    int cover;

    double len;

};

node tree[];

double yy[];

int n,len;

struct Line

{

    double y_down;

    double y_up;

    double x;

    int cover;

};

Line line[];

int cmp(Line a,Line b)

{

    return a.x<b.x;

}

int find(double x)

{

    int l=,r=len,mid;

    while(l<=r)

    {

        mid=(l+r)/;

        if(yy[mid]==x)

            return mid;

        if(yy[mid]<x)

            l=mid+;

        else

            r=mid-;

    }

    return l;

}

void build(int i,int l,int r)

{

    tree[i].l=l;

    tree[i].r=r;

    tree[i].cover=;

    tree[i].len=;

    if(l+==r)

        return;

    int mid=(l+r)/;

    build(*i,l,mid);

    build(*i+,mid,r);

}

void fun(int i)

{

    if(tree[i].cover)

        tree[i].len=yy[tree[i].r]-yy[tree[i].l]; //如果cover大于1，那么整段都可用于与下一线段求并面积

    else if(tree[i].l+==tree[i].r) //叶子线段

        tree[i].len=;

    else

        tree[i].len=tree[*i].len+tree[*i+].len; //很简单的dp

}

void updata(int i,int l,int r,int cover)

{

    if(tree[i].l>r || tree[i].r<l)

        return;

    if(tree[i].l>=l && tree[i].r<=r)

    {

        tree[i].cover+=cover;

        fun(i);

        return;

    }

    updata(*i,l,r,cover);

    updata(*i+,l,r,cover);

    fun(i);

}

int main()

{

    double x1,y1,x2,y2;

    int i,m,a,b,cas=;

    freopen("in.txt","r",stdin);

    while(scanf("%d",&n)== && n)

    {

        m=;

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

        {

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            yy[m]=y1;

            line[m].cover=;

            line[m].x=x1;

            line[m].y_down=y1;

            line[m++].y_up=y2;

            yy[m]=y2;

            line[m].cover=-;

            line[m].x=x2;

            line[m].y_down=y1;

            line[m++].y_up=y2;

        }

        sort(yy,yy+m);

        len=;

        for(i=;i<m;i++)

        {

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

                yy[len++]=yy[i];

        }

        len--;

        build(,,len);

        sort(line,line+m,cmp);

        double ans=;

        printf("Test case #%d\n",cas++);

        for(i=;i<m-;i++)

        {

            a=find(line[i].y_down);

            b=find(line[i].y_up);

            updata(,a,b,line[i].cover);

            ans+=tree[].len*(line[i+].x-line[i].x);  //tree[1].len已经保留了整个树与line[i+1]所能求并面积的长度

        }

        printf("Total explored area: %0.2lf\n\n",ans);

    }

    return ;

}

相关文章