Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这规模哪里需要线段树，直接枚举X方向区间，然后Y方向进行区间合并

Posted by 00648057 at 2017-03-29 06:32:46 on Problem 1151
```每个方向上最多200个坐标，复杂度最多也就200 * 200

#include <stdio.h>
#include <vector>
#include <algorithm>

const int L = 100;
double x1[L], x2[L], y1[L], y2[L];

class YSegment {
public:
double y_begin, y_end;
bool available;
bool operator < (const YSegment &rhs) const {
return this->y_begin < rhs.y_begin;
}
YSegment(double y1, double y2, bool a) {
y_begin = y1;
y_end = y2;
available = a;
}
};

void processCase(int caze, int n) {
std::vector<double> x_coor(2 * L);
for (int i = 0; i < n; i++) {
x_coor.push_back(x1[i]);
x_coor.push_back(x2[i]);
}
std::sort(x_coor.begin(), x_coor.end());

double area = 0.0;
for (int j = 0; j < x_coor.size() - 1; j++) {
double x_left = x_coor[j], x_right = x_coor[j + 1];
if (x_left == x_right) continue;

// Sort Y segments.
std::vector<YSegment> y_segs;
for (int i = 0; i < n; i++) {
if (x_left >= x1[i] && x_right <= x2[i]) {
YSegment y_seg(y1[i], y2[i], true);
y_segs.push_back(y_seg);
}
}
std::sort(y_segs.begin(), y_segs.end());

// Combine Y segments
for (int i = 1; i < y_segs.size(); i++) {
// Find the previous available segment.
int p = i - 1;
while (!y_segs[p].available) p--;
if (y_segs[i].y_begin <= y_segs[p].y_end) {
y_segs[i].available = false;
y_segs[p].y_end = std::max(y_segs[p].y_end, y_segs[i].y_end);
}
}

// Accumulate Y segments
double y_length = 0.0;
for (int i = 0; i < y_segs.size(); i++) {
if (y_segs[i].available) {
y_length += y_segs[i].y_end - y_segs[i].y_begin;
}
}

area += (x_right - x_left) * y_length;
}

printf("Test case #%d\nTotal explored area: %.2lf\n\n", caze, area);
}

int main() {
int n;
int caze = 0;
while (true) {
scanf("%d", &n);
if (n == 0) break;
caze++;
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &x1[i], &y1[i], &x2[i], &y2[i]);
}
processCase(caze, n);
}
}```

Followed by: