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  
      求矩形的並的總面積
*********************************************************************/

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

在網上看到有的ACMER把程序分為輸入、解決問題、輸出的三層結構，覺得挺好的，打算以後也這麼做，免得全擠在一個main裡，而且這樣也便於調試。我盡量不用全局變量，這樣各函數調用時消息的傳遞就很明確了。