POJ 1151 Atlantis（离散化+扫描线）

题目大意：

求N个矩形的并的总面积。

参考了黑书上讲离散化的那两页，想到了上学期学的计算机图形学里的多边形填充算法。

src:

[cpp]
/********************************************************************
    created:    2013/03/28
    created:    28:3:2013   11:43
    filename:   H:\PE\USA\POJ.1151.Atlantis.cpp
    file path: H:\PE\USA
    file base: POJ.1151.Atlantis
    file ext:   cpp
    author:     Justme0
                   求矩形的并的总面积
*********************************************************************/

// #define ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cassert>
using namespace std;

// 水平线段
struct Horizon {
    double xL; // 左端点的横坐标
    double xR; // 右端点的横坐标
    double y;   // 水平线的纵坐标
    bool isUp; // 矩形的上边or下边

    Horizon() : xL(0), xR(0), y(0), isUp(false) {}

    Horizon(double _xL, double _xR, double _y, bool _isUp)
        : xL(_xL),
        xR(_xR),
        y(_y),
        isUp(_isUp) {}

    bool operator<(const Horizon &other) const {
        return this->y < other.y;
    }
};

// 返回：输入是否结束
bool input(vector<double> &xVec, vector<Horizon> &hrzVec)
{
    int cnt;
    cin >> cnt;
    if (0 == cnt) {
        return false;
    }
    double Ax, Ay, Bx, By;
    while (cnt--) {
        cin >> Ax >> Ay >> Bx >> By;
        xVec.push_back(Ax);
        xVec.push_back(Bx);
        hrzVec.push_back(Horizon(Ax, Bx, Ay, false));
        hrzVec.push_back(Horizon(Ax, Bx, By, true));
    }
    return true;
}

void solve(vector<double> &xVec, const vector<Horizon> &hrzVec, double &result)
{
    result = 0;
    sort(xVec.begin(), xVec.end());
    xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
    sort(hrzVec.begin(), hrzVec.end());

    for (vector<double>::size_type i = 0; i < xVec.size() - 1; ++i) {
        double L = xVec[i];
        double R = xVec[i + 1];
        double width = R - L;
        assert(width > 0);   // 等于0的已unique

        int count = 0; // 计数器，正数表示被覆盖，0表示未被覆盖（有count个矩形覆盖了该区域）
        Horizon former;
        for (vector<Horizon>::size_type j = 0; j < hrzVec.size(); ++j) {
            Horizon current = hrzVec[j];
            if (current.xL <= L && R <= current.xR) {
                assert(count >= 0);
                if (count > 0) {
                    double height = current.y - former.y;
                    assert(height >= 0);
                    result += width * height;
                }
                former = current;
                current.isUp ? --count : ++count;
                assert(count >= 0);
            }
        }
        assert(count == 0);
    }
}

void output( int testCase, double result )
{
    printf("Test case #%d\nTotal explored area: %.2f\n\n", testCase, result);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("cin.txt", "r", stdin);
#endif

    for (int testCase = 1; ; ++testCase) {
        vector<double> xVec;
        vector<Horizon> hrzVec;
        if (!input( xVec, hrzVec)) {
            break;
        }
        double result = 0;
        solve(xVec, hrzVec, result);
        output(testCase, result);
    }

    return 0;
}

/********************************************************************
created: 2013/03/28
created: 28:3:2013   11:43
filename: H:\PE\USA\POJ.1151.Atlantis.cpp
file path: H:\PE\USA
file base: POJ.1151.Atlantis
file ext: cpp
author:  Justme0
  &nbs

补充：软件开发 , C++ ,