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

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

问题链接:https://vjudge.net/problem/UVA-221

Solution:

按照紫书上的方法写的,所以只记录一点个人理解。数据取值范围是实数域,枚举x坐标无法做到,所以我们将x坐标离散化,专门开一个数组,存储所有端点x坐标,从小到大排序,去重【可以使用unique函数】,构成了一个无重复端点值数组,由于数据量不大, 可以对于每个建筑物都暴力找它在那个区间中,对于每个建筑物,都暴力判断它是否被遮挡,得益于离散化,这个端点数组中任意两个相邻值之间不存在额外的端点,因此这中间任意一个数值坐标都可以用来判断一个建筑是否包含这组端点,这里可以取中点,能很大程度上避免浮点误差的问题。

#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;
}