## 【UVA-221】Urban Elevations【紫书】【离散化】

【UVA-221】Urban Elevations【紫书】【离散化】

Solution:

```#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int LIM = 100 + 10;
const double EPS = 1e-6;
struct Building{
int id;
double x, y, w, h;
bool operator < (const Building &p) {
if (x != p.x) return x < p.x;
return y < p.y;
}
} builds[LIM];
double points[LIM * 2];
int gblCnt, n;

inline void init() {
memset(points, 0, sizeof points);
memset(builds, 0, sizeof builds);
gblCnt = 1;
}

inline bool isInRange(int idx, double pos) {
return builds[idx].x <= pos && pos <= builds[idx].x + builds[idx].w;
}

bool isVisible(int idx, double mid) {
for (int i = 0; i < n; i++) {
if (i == idx) continue;
if (builds[i].y < builds[idx].y && builds[i].h >= builds[idx].h && isInRange(i, mid))
return false;
}
return true;
}

int main(void) {
for (int k = 1; ~scanf("%d", &n) && n; k++) {
init();
if (k - 1) putchar('\n');
printf("For map #%d, the visible buildings are numbered as follows:\n", k);
for (int i = 0; i < n; i++) {
scanf("%lf%lf%lf%*lf%lf", &builds[i].x, &builds[i].y, &builds[i].w, &builds[i].h);
builds[i].id = i + 1;
points[i << 1] = builds[i].x, points[(i << 1) + 1] = builds[i].x + builds[i].w;
}
sort(points, points + n * 2);
sort(builds, builds + n);
int len = unique(points, points + n * 2) - points;
printf("%d", builds[0].id);
for (int i = 1; i < n; i++) {
for (int j = 1; j < len; j++) {
int mid = (points[j] + points[j - 1]) / 2;
if (!isInRange(i, mid)) continue;
if (isVisible(i, (points[j] + points[j - 1]) / 2)) {
printf(" %d", builds[i].id);
break;
}
}
}
putchar('\n');
}
return 0;
}
```