原题链接
更好的阅读体验

题目描述

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。

您的朋友Bill必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。

输入格式
输入包含多组测试用例。

对于每组测试用例，第一行包含整数n，表示总的地图数量。

接下来n行，描绘了每张地图，每行包含四个数字$x1,y1,x2,y2$（不一定是整数）,$(x1,y1)$和$(x2,y2)$分别是地图的左上角位置和右下角位置。

当输入用例$n=0$时，表示输入终止，该用例无需处理。

输出格式
每组测试用例输出两行。

第一行输出”Test case #k”，其中k是测试用例的编号，从1开始。

第二行输出“Total explored area：a”，其中a是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。

在每个测试用例后输出一个空行。

数据范围
$1≤n≤100$
$0≤x_1<x_2≤100000$
$0≤y_1<y_2≤100000$

样例

输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00 

线段树+扫描线+二分查找+离散化

这道题目是真的有毒还是我太菜了,各种算法大杂烩,最后还是看了五篇优秀的blog东凑西凑才理解的.为什么我要自告奋勇写这道题目,可见出题人的内心有多么友好啊......

离散化:首先坐标太大了,我们需要离散化.

二分:既然离散化了,自然就要二分找坐标了.

扫描线:题目告诉我们,需要将二维转化成为一维,所以我们需要扫描线这种变态级别神器来解答这道题目.具体来说,我们就是要取出N个矩阵的左右边界,然后从下往上或者从左往右的方向,不断地扫描,然后我们就会求出每一条扫描线在矩阵上覆盖的长度L,然后这一段面积就是L*宽度.

我觉得自己讲得不好,主要是思路也有些混乱,所以给出几位网上大佬的题解,希望能让各位不浪费点击我这条博客的流量,虽然图片很多.手动滑稽

以下为riba大佬的优秀讲解,个人觉得很好的一篇blog

现在假设我们有一根线，从下往上开始扫描
如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。






我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为1，上面的边标记为-1，每遇到一个矩形时，我们知道了标记为1的边，我们就加进来这一条矩形的长，等到扫描到-1时，证明这一条边需要删除，就删去，利用1和-1可以轻松的到这种状态。
还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的时候r+1和r-1
再提一下离散化，离散化就是把一段很大的区间映射到一个小区间内，这样会节省大量空间，要进行离散化，我们先对端点进行排序，然后去重，然后二分找值就可以了

以下为另外一位大佬的blog
这道题我一直在纠结，怎么求当前有扫描线上有的线段总长？怎么lazy下放？我一直想的是每个点维护的都是它维护的这个区间内的总的cnt等等。
后来我发现换个思路，一切都很简单！
我的每个节点t[x].l~t[x].r维护的其实是线段t[x].l~(t[x].r+1)，也就是若干条线段，因为点分成左右孩子的时候会有问题（比如[3,3]维护的到底是什么？）。
我们要把每个节点看成是一条线段。
对于每个节点维护两个值：
cnt：这个点所代表的线段被覆盖了多少次。
len：以这个点为根的子树中被覆盖的区间一共有多长。
当一条线段进来的时候，在代表它的那若干个节点上cnt++，其它节点cnt不用加。
然后len维护的就是这个区间内那些cnt>0的节点所覆盖的区间总长。
其实线段树上每个节点都可以有它的实际意义

C++ 代码

//这道题目码风有些诡异,虽然我已经尽量变成我这种通俗易懂的码风了.
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
double dis[N];
struct node
{
    double x1,x2,h;
    int f;
    void init(double l2,double r2,double h2,int key)
    {
        x1=l2;
        x2=r2;
        h=h2;
        f=key;
    }
} line[N];
struct line_tree
{
    int l,r,f;
    double len;
} t[N<<2];
int cmp(node a,node b)
{
    return a.h<b.h;
}
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    t[p].f=0;
    t[p].len=0;
    if (l==r)
        return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build((p<<1)+1,mid+1,r);
}
void get_len(int p)
{
    if (t[p].f>=1)
        t[p].len=dis[t[p].r+1]-dis[t[p].l];//这里记得+1
    else    
        t[p].len=t[p<<1].len+t[(p<<1)|1].len;
}
void change(int p,int l,int r,int v)
{
    if (t[p].l==l && r==t[p].r)
    {
        t[p].f+=v;
        get_len(p);
        return ;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if (r<=mid)
        change(p<<1,l,r,v);
    else if (l>mid)
        change((p<<1)+1,l,r,v);
    else
    {
        change(p<<1,l,mid,v);
        change((p<<1)+1,mid+1,r,v);
    }
    get_len(p);
}
int find(double p,int l,int r)//诡异版二分
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if (dis[mid]==p)
            return mid;
        if (dis[mid]<p)
            l=mid+1;
        else
            r=mid-1;
    }
}
int main()
{
    int ts=0,n;
    while(scanf("%d",&n)!=EOF)
    {
        if (n==0)
            break;
        printf("Test case #%d\n",(++ts));
        int num=0;
        for(int i=0;i<n;i++)
        {
            double x1,x2,y1,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[num].init(x1,x2,y1,1);
            dis[num++]=x1;
            line[num].init(x1,x2,y2,-1);
            dis[num++]=x2;
        }
        sort(line,line+num,cmp);
        sort(dis,dis+num);
        int dis_num=unique(dis,dis+num)-dis;
        build(1,0,dis_num-1);
        double ans=0;
        for(int i=0;i<num-1;i++)
        {
            int line_l=find(line[i].x1,0,dis_num);
            int line_r=find(line[i].x2,0,dis_num)-1;
            change(1,line_l,line_r,line[i].f);
            ans=ans+t[1].len*(line[i+1].h-line[i].h);
        }
        printf("Total explored area: %.2lf\n\n",ans);
    }
    return 0;
}