|
|
題目鏈接：http://poj.org/problem?id=1151
  /**//*
 題意：
給定n(n <= 100)個矩形，求它們的面積并。
解法：
離散化+線段樹 或者 離散化+FloodFill
思路：
數(shù)據(jù)量很小，直接把浮點數(shù)離散成整點，然后暴力FloodFill，最后統(tǒng)計
覆蓋的塊的實際面積。
也可以采用線段樹，具體解法如下面這題：
http://www.shnenglu.com/menjitianya/archive/2011/03/29/142972.html
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define eps 1e-6
#define maxn 100000
// 垂直x軸的線段
struct VLine  {
double x;
double y1, y2; // y1 <= y2
int val; // in or out
  VLine() {}
VLine(double _x, double _y1, double _y2, int _v) {
x = _x;
y1 = _y1;
y2 = _y2;
val = _v;
 }
};
vector <VLine> Inc;
double tmp[maxn], bin[maxn];
int tmpsize, binsize;
bool cmp(VLine a, VLine b) {
return a.x < b.x;
}
void preBinaryProcess() {
sort(tmp, tmp + tmpsize);
binsize = 0;
bin[ ++binsize ] = tmp[0];
int i;
for(i = 1; i < tmpsize; i++) {
if(fabs(tmp[i] - tmp[i-1]) > eps)
bin[ ++binsize ] = tmp[i];
}
}
int Binary(double val) {
int l = 1;
int r = binsize;
int m;
while(l <= r) {
m = (l + r) >> 1;
if(fabs(val - bin[m]) < eps)
return m;
if(val > bin[m]) {
l = m + 1;
}else
r = m - 1;
}
}
struct Tree {
int nCover; // 當(dāng)前線段被完全覆蓋了幾次
double yLen; // 測度、相鄰掃描線間y方向的有效長度
int l, r; // 線段樹該結(jié)點管理的區(qū)間
int nowIndex; // 當(dāng)前結(jié)點所在的數(shù)組下標(biāo)
void Update() {
if(nCover > 0) {
yLen = bin[r] - bin[l];
}else {
if(l + 1 == r)
yLen = 0;
else {
yLen = T[nowIndex<<1].yLen + T[nowIndex<<1|1].yLen;
}
}
}
int GetMid() {
return (l + r) >> 1;
}
}T[maxn*4];
void Build(int p, int l, int r) {
T[p].nCover = T[p].yLen = 0;
T[p].l = l; T[p].r = r;
T[p].nowIndex = p;
if(l == r || l + 1 == r)
return ;
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid, r);
}
void Insert(int p, int l, int r, int val) {
if(l <= T[p].l && T[p].r <= r) {
T[p].nCover += val;
T[p].Update();
return ;
}
int mid = T[p].GetMid();
if(l < mid) {
Insert(p<<1, l, r, val);
}
if(r > mid) {
Insert(p<<1|1, l, r, val);
}
T[p].Update();
}
int n;
int main() {
int i;
int Case = 1;
while(scanf("%d", &n) != EOF && n) {
Inc.clear();
tmpsize = binsize = 0;
for(i = 0; i < n; i++) {
double x1, y1, x2, y2;
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
Inc.push_back(VLine(x1, y1, y2, 1));
Inc.push_back(VLine(x2, y1, y2, -1));
tmp[ tmpsize++ ] = y1;
tmp[ tmpsize++ ] = y2;
}
sort(Inc.begin(), Inc.end(), cmp);
preBinaryProcess();
Build(1, 1, binsize);
double ans = 0;
for(i = 0; i < Inc.size(); i++) {
int y1 = Binary(Inc[i].y1);
int y2 = Binary(Inc[i].y2);
if(y1 == y2)
continue;
if(i)
ans += (Inc[i].x - Inc[i-1].x) * T[1].yLen;
Insert(1, y1, y2, Inc[i].val);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", Case++, ans);
}
return 0;
}
|