codevs3044 矩形面积求并(线段数+扫描线+离散化)

题目描述 Description
输入n个矩形,求他们总共占地面积(也就是求一下面积的并)
输入描述 Input Description
可能有多组数据,读到n=0为止(不超过15组)
每组数据第一行一个数n,表示矩形个数(n<=100)
接下来n行每行4个实数x1,y1,x2,y1(0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000),表示矩形的左下角坐标和右上角坐标
输出描述 Output Description
每组数据输出一行表示答案
样例输入 Sample Input
C++
2
10 10 20 20
15 15 25 25.5
0
1
2
3
4
2
10 10 20 20
15 15 25 25.5
0
样例输出 Sample Output
C++
180.00
1
180.00

``` wtf,挣扎了好久发现没问题啊,原来是之前的数组弄成int,换成double过来就a了。
这道题是线段树加扫描线。
第一次做线段树+扫描线的题目,也是第一次接触扫描线这词眼。
其实扫描线很好理解啊,就是一条线,你从左扫到右,或者从下扫到上边。
不过这里不太容易理解。
我们需要解决的问题有很多。
如何排除重叠部分的面积,搞来搞起,说复杂是复杂,不太容易理解。
具体怎么搞用文字能难描述:
具体就是:
首先呢,扫描线,我们这里是从下往上扫描。
这里我们记录一下这个边左右两点的坐标,排一下序即可。(还有就是记录矩形的上下边,这里我们
从下往上扫,下边为1,上边为-1)
然后我们记录下横坐标,排一下序,记得取重,这里我调用了unique去重,这里离散化一下。
然后这是准备步骤,接下来就是写线段树了。
继续呢,看代码。
具体是这么计算的呢:安利一篇文章

传送门:
传送门:

关于离散化(转):
有些数据本身很大, 自身无法作为数组的下标保存对应的属性。
如果这时只是需要这堆数据的相对属性, 那么可以对其进行离散化处理!
离散化:当数据只与它们之间的相对大小有关,而与具体是多少无关时,可以进行离散化。
例如
9 1 0 5 45 2 1 4 3 的逆序对个数相同。
设有4个数:
123456712345678912345678123456
排序:123456<1234567<12345678<123456789
 =>   1    <     2     <      3     <    4
那么这4个数可以表示成:2431
使用STL算法离散化:
思路:先排序,再删除重复元素,然后就是索引元素离散化后对应的值。
假定待离散化的序列为a[n],b[n]是序列a[n]的一个副本,则对应以上三步为:
sort(sub_a,sub_a+n);
int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数
for(i=0;i<n;i++)
    a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值
对于第3步,若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound,从1, 2, 3, ..., size则用upper_bound,其中lower_bound返回第1个不小于b[i]的值的指针,而upper_bound返回第1个大于b[i]的值的指针,当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果,两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<ctime>
#include<string>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#include<set>
#include<map>
#include<cstdio>
#include<limits.h>
#define MOD 1000000007
#define fir first
#define sec second
#define fin freopen("/home/ostreambaba/文档/input.txt", "r", stdin)
#define fout freopen("/home/ostreambaba/文档/output.txt", "w", stdout)
#define mes(x, m) memset(x, m, sizeof(x))
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define INF 1e9+7
#define Pi 4.0*atan(1.0)

#define lowbit(x) (x&(-x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-12;
const int maxn = 100100;
const int maxm = 200010;
using namespace std;
struct edg{
    double l,r,h; //矩形的左右节点坐标和高
    int f; //1表示下边 -1表示上边
    edg(){}
    edg(double x1,double x2,double h1,int f1):l(x1),r(x2),h(h1),f(f1){}
    bool operator<(const edg &t)const{ //从低到高排序
        return h<t.h;
    }
}ed[maxn];
double sum[maxn<<2];
int cnt[maxn<<2];
double x[maxn];
inline void PushUp(int rt,int l,int r)
{
    if(cnt[rt]){
        sum[rt]=x[r+1]-x[l];
    }
    else if(l==r){
        sum[rt]=0;
    }
    else{
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
}
inline void buildTree(int l,int r,int rt)
{
    sum[rt]=cnt[rt]=0;
    if(l==r){
        return;
    }
    int m=(l+r)>>1;
    buildTree(lson);
    buildTree(rson);
}
inline void update(int L,int R,int l,int r,int rt,int equal)
{
    if(L<=l&&r<=R){
        cnt[rt]+=equal;
        PushUp(rt,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m){
        update(L,R,lson,equal);
    }
    if(R>m){
        update(L,R,rson,equal);
    }
    PushUp(rt,l,r);
}
int main()
{
    int N;
    double x1,x2,y1,y2;
    while(~scanf("%d",&N)&&N){
        int tot=0;
        for(int i=0;i<N;++i){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            edg &t1=ed[tot],&t2=ed[tot+1];
            t1.l=t2.l=x1;
            t1.r=t2.r=x2;
            t1.h=y1,t2.h=y2;
            t1.f=1,t2.f=-1;
            x[tot]=x1,x[tot+1]=x2;
            tot+=2;
        }
        sort(ed,ed+tot); //对矩形进行排序 按高来排序 因为扫描线从下往上扫
        sort(x,x+tot);
        int k=unique(x,x+tot)-x; //取重,对坐标进行离散化
        buildTree(0,k-1,1);
        double res=0;
        for(int i=0;i<tot;++i){
            int l=lower_bound(x,x+k,ed[i].l)-x;
            int r=lower_bound(x,x+k,ed[i].r)-x-1;
            if(l<=r){
                update(l,r,0,k-1,1,ed[i].f);
            }
            res+=(ed[i+1].h-ed[i].h)*sum[1];
        }
        printf("%.2f\n",res);
    }
    return 0;
}
    原文作者:_ostreamBaba
    原文地址: https://blog.csdn.net/Viscu/article/details/53455759
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞