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

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 ;
}