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

// 水平线段
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 &xVec, vector &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 &xVec, const vector &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::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::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 xVec;
vector hrzVec;
if (!input( xVec, hrzVec)) {
break;
}
double result = 0;
solve(xVec, hrzVec, result);
output(testCase, result);
}

return 0;
}

在网上看到有的ACMER把程序分为输入、解决问题、输出的三层结构，觉得挺好的，打算以后也这么做，免得全挤在一个main里，而且这样也便于调试。我尽量不用全局变量，这样各函数调用时消息的传递就很明确了。