这题本来可以不用线段树做的，因为数据比较弱，直接离散化即可。但为了练习线段树，还是用线段树打了，可是却WA了一整天！调了四个小时以后仍没找出错误，让竹子帮我测试，测出了一处错误，又去北大讨论版找了些数据测，终于过了。
我的代码如下，第一次写这类题目，写得比较乱，以后再改进吧。
/*
* hdu1542/linux.cpp
* Created on: 2011-9-1
* Author : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef struct CNode {
int L, R;
int covers;
double lastx;
CNode *pLeft, *pRight;
} CNode;
typedef struct {
double x;
double yi;
double ya;
int cover;
} Line;
const int MAXN = 205;
const int MAX_NODE = 4 * MAXN;
CNode Tree[MAX_NODE];
Line lines[2 * MAXN];
double ys[2 * MAXN], ans;
int N, N2, nCount;
inline bool operator<(const Line &a, const Line &b) {
return a.x < b.x;
}
//建立线段树
void BuildTree(CNode *pRoot, int L, int R) {
pRoot->L = L;
pRoot->R = R;
pRoot->covers = 0;
pRoot->lastx = 0;
if (L == R) {
return;
}
nCount++;
pRoot->pLeft = Tree + nCount;
nCount++;
pRoot->pRight = Tree + nCount;
int mid = (L + R) / 2;
BuildTree(pRoot->pLeft, L, mid);
BuildTree(pRoot->pRight, mid + 1, R);
}
//插入数据
void Update(CNode *pRoot, double i, double v, double x, int cover) {
if (pRoot->L == pRoot->R) {
if (pRoot->covers) {
ans += (ys[pRoot->R] - ys[pRoot->L - 1]) * (x - pRoot->lastx);
}
pRoot->covers += cover;
pRoot->lastx = x;
return;
}
int mid = (pRoot->L + pRoot->R) / 2;
if (pRoot->covers) {
Update(pRoot->pLeft, ys[pRoot->L - 1], ys[mid], pRoot->lastx,
pRoot->covers);
Update(pRoot->pRight, ys[mid], ys[pRoot->R], pRoot->lastx,
pRoot->covers);
pRoot->covers = 0;
}
if (ys[mid] > i && ys[mid] < v) {
Update(pRoot->pLeft, i, ys[mid], x, cover);
Update(pRoot->pRight, ys[mid], v, x, cover);
} else if (ys[mid] >= v) {
Update(pRoot->pLeft, i, v, x, cover);
} else {
Update(pRoot->pRight, i, v, x, cover);
}
}
void work() {
int T = 0;
double xi, yi, xa, ya;
while (scanf("%d", &N) == 1 && N > 0) {
N2 = 0;
for (int i = 0; i < N; i++) {
scanf("%lf%lf%lf%lf", &xi, &yi, &xa, &ya);
lines[N2].yi = yi;
lines[N2].ya = ya;
lines[N2].cover = 1;
lines[N2].x = xi;
ys[N2++] = yi;
lines[N2].yi = yi;
lines[N2].ya = ya;
lines[N2].cover = -1;
lines[N2].x = xa;
ys[N2++] = ya;
}
nCount = 0;
BuildTree(Tree, 1, N2 - 1);
sort(ys, ys + N2);
sort(lines, lines + N2);
ans = 0;
for (int i = 0; i < N2; i++) {
Update(Tree, lines[i].yi, lines[i].ya, lines[i].x, lines[i].cover);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n", ++T, ans);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
work();
return 0;
}
下面是我的测试数据，希望对以后做此题不过者有用。
输入数据：
2 1 2 6 3 3 1 4 5 5 137 10 275 20 296 201 306 275 265 105 497 115 233 74 402 84 296 10 402 147 5 1.37 0.10 2.75 0.20 2.96 2.01 3.06 2.75 2.65 1.05 4.97 1.15 2.33 0.74 4.02 0.84 2.96 0.10 4.02 1.47 3 1 1 6 7 4 2 11 5 2 0 8 3 3 1 1 3 3 2 2 6 6 0 0 4 4 3 3 3 4 4 1 1 5 5 2 2 3 3 3 1 1 4 4 2 2 3 3 10 10 20 20 2 1 1 4 4 2 2 3 3 3 15 15 25 25.5 10 10 20 20 15 15 20 20 2 1 1 2 2 2 2 3 3 1 1 1 2 2 2 10 10 20 20 10 20 20 30 3 10 10 20 20 15 15 25 25.5 30 10 40 20 2 15 15 25 25.5 10 10 20 20 8 9.33 19.52 30.44 24.39 8.06 29.38 9.75 51.77 22.38 15.06 32.35 33.30 30.66 19.20 44.13 19.62 17.93 15.38 39.35 41.58 9.65 6.47 29.80 10.39 26.20 24.61 40.63 35.85 25.25 12.51 29.80 36.17 8 157.98 278.30 246.25 501.22 152.89 15.06 355.43 214.74 61.53 56.12 141.85 96.97 21.43 303.77 250.07 329.65 5.83 115.65 306.10 211.88 275.44 132.52 353.21 276.49 149.71 175.49 271.40 379.94 127.42 32.57 187.05 282.22 0
输出数据如下
Test case #1 Total explored area: 8.00 Test case #2 Total explored area: 18532.00 Test case #3 Total explored area: 1.85 Test case #4 Total explored area: 53.00 Test case #5 Total explored area: 28.00 Test case #6 Total explored area: 16.00 Test case #7 Total explored area: 109.00 Test case #8 Total explored area: 9.00 Test case #9 Total explored area: 180.00 Test case #10 Total explored area: 2.00 Test case #11 Total explored area: 1.00 Test case #12 Total explored area: 200.00 Test case #13 Total explored area: 280.00 Test case #14 Total explored area: 180.00 Test case #15 Total explored area: 751.10 Test case #16 Total explored area: 99910.16