HDU 1542 Atlantis(扫描线)

Description:

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input:

The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.

The input file is terminated by a line containing a single 0. Don’t process it.

Output:

For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.

Output a blank line after each test case.

Sample Input:

2
10 10 20 20
15 15 25 25.5
0

Sample Output:

Test case #1
Total explored area: 180.00

题目链接

给出 $个矩形，求所有矩形并集的面积$

矩形面积并换句话说就是扫描线裸（板子）题

首先离散化横坐标，将所有矩形的上下边界按照纵坐标升序排序

按照纵坐标升序的次序从下向上扫描矩形的面积

按照样例的图像来理解一下

扫描线第一次从直线 $开始扫描，保存线段长度，第二次扫描线扫描到直线，这样就可以把矩形已经扫过的矩形面积计入结果，再更新线段长度，第三次扫描到直线，再将扫过的矩形面积计入结果更新线段长度，最后一次扫描到直线将扫过矩形面积计入结果就可以得出这两个矩形的面积并了。$

扫描线中可以用线段树维护上一次扫描线扫描到的线段长度的存在位置

推荐一篇具体详解博客

线段树辅助——扫描线法计算矩形面积并

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int maxn = 1e2 + 5;
const db eps = 1e-9;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
int Cmp(db Key1, db Key2) {return Sgn(Key1 - Key2);}

struct Segment {
    db Left, Right;
    db Height;
    int Flag;
};
bool operator < (Segment &Key1, Segment &Key2) {return Cmp(Key1.Height, Key2.Height) < 0;}
vector<Segment> Seg;

vector<db> Pos;

int BinarySearch(db Key) {
    int Res = Pos.size() - 1, Left = 0, Right = Pos.size() - 1;
    while (Left <= Right) {
        int Mid = (Left + Right) >> 1;
        if (Cmp(Pos[Mid], Key) >= 0) {
            Res = Mid;
            Right = Mid - 1;
        }
        else {
            Left = Mid + 1;
        }
    }
    return Res;
}

struct Node {
    int Left, Right;
    int Cnt;
    db Len;
};
Node SGT[maxn << 4];

void PushUp(int Root) {
    if (SGT[Root].Cnt) SGT[Root].Len = Pos[SGT[Root].Right + 1] - Pos[SGT[Root].Left];
    else if (SGT[Root].Left == SGT[Root].Right) SGT[Root].Len = 0.0;
    else SGT[Root].Len = SGT[Root << 1].Len + SGT[Root << 1 | 1].Len;
}

void Build(int Left, int Right, int Root) {
    SGT[Root].Left = Left; SGT[Root].Right = Right;
    SGT[Root].Cnt = 0; SGT[Root].Len = 0.0;
    if (Left == Right) return;
    int Mid = (Left + Right) >> 1;
    Build(Left, Mid, Root << 1);
    Build(Mid + 1, Right, Root << 1 | 1);
    PushUp(Root);
}

void Update(int Left, int Right, int Value, int Root) {
    if (Left <= SGT[Root].Left && Right >= SGT[Root].Right) {
        SGT[Root].Cnt += Value;
        PushUp(Root);
        return;
    }
    int Mid = (SGT[Root].Left + SGT[Root].Right) >> 1;
    if (Right <= Mid) Update(Left, Right, Value, Root << 1);
    else if (Left > Mid) Update(Left, Right, Value, Root << 1 | 1);
    else {
        Update(Left, Mid, Value, Root << 1);
        Update(Mid + 1, Right, Value, Root << 1 | 1);
    }
    PushUp(Root);
}

int Case;
int N;
db X1, Y1, X2, Y2;
db Ans;

int main(int argc, char *argv[]) {
    while (~scanf("%d", &N) && N) {
        Seg.clear(); Pos.clear();
        for (int i = 0; i < N; ++i) {
            scanf("%lf%lf%lf%lf", &X1, &Y1, &X2, &Y2);
            Seg.push_back((Segment){X1, X2, Y1, 1});
            Seg.push_back((Segment){X1, X2, Y2, -1});
            Pos.push_back(X1); Pos.push_back(X2);
        }
        sort(Seg.begin(), Seg.end());
        sort(Pos.begin(), Pos.end(), [&](db Key1, db Key2) {return Cmp(Key1, Key2) < 0;});
        int Cur = 1;
        for (int i = 1; i < (int)Pos.size(); ++i)
            if (Cmp(Pos[i], Pos[i - 1]) != 0)
                Pos[Cur++] = Pos[i];
        Pos.erase(Pos.begin() + Cur, Pos.end());
        Build(0, (int)Pos.size(), 1);
        Ans = 0.0;
        for (int i = 0; i < (int)Seg.size() - 1; ++i) {
            int Left = BinarySearch(Seg[i].Left), Right = BinarySearch(Seg[i].Right);
            Update(Left, Right - 1, Seg[i].Flag, 1);
            Ans += (Seg[i + 1].Height - Seg[i].Height) * SGT[1].Len;
        }
        printf("Test case #%d\n", ++Case);
        printf("Total explored area: %.2lf\n\n", Ans);
    }
    return 0;
}