问题描述
p221原题链接:UVaOJ 221 - Urban Elevations
相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-12
解法一:排序 + 离散化
题目要求输出需要按照自定义顺序排序,因此自定义 Building 结构体时重载一下 < 运算符,接下来就可以遍历处理,关键在于如何判断当前的建筑物是否可见 —— 由于观察视角是正前方,因此可以根据东西方向的 x 轴进行离散化采样,得到用于判断的所有可能坐标 mx (因为所有出现的 x 与 x+w 坐标是已知的,我们只需要把这个方向的所有坐标整理出来,对于每个单独的区间去判断当前建筑物是否可见即可, mx 可以随机从每个区间中取,最简单的做法就是取中点)。对于给定的 mx ,想要判断某个建筑在这个位置是否可见,只需要验证是否有其它建筑物进行了遮挡即可,遮挡的条件是:1. 位置比当前建筑物更靠近南方向;2. 高度比当前建筑物高。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; struct Building { int id; double x, y, w, d, h; bool operator<(const Building& rhs) const { return (x < rhs.x) || (x == rhs.x && y < rhs.y); } bool cover(const double mx) const { return (x <= mx) && (x + w >= mx); } bool behind(const Building& rhs) const { return (rhs.y < y) && (rhs.h >= h); } }; bool visible(const Building& cur, const vector<Building>& building, double mx) { if (!cur.cover(mx)) return false; for (auto& b : building) // check if any building is behind if (cur.behind(b) && b.cover(mx)) return false; return true; } int main() { int map_count = 0, building_count = 0; while (cin >> building_count && building_count) { vector<Building> buildings; set<double> x_coord; for (int id = 1; id <= building_count; ++id) { double x, y, w, d, h; cin >> x >> y >> w >> d >> h; buildings.push_back({id, x, y, w, d, h}); // id is 1-based x_coord.insert({x, x + w}); } sort(buildings.begin(), buildings.end()); // for output in order vector<double> x_occur(x_coord.begin(), x_coord.end()); vector<double> mx_occur; for (int i = 0; i < x_occur.size() - 1; ++i) mx_occur.push_back((x_occur[i] + x_occur[i + 1]) / 2); cout << (map_count ? "\n" : "") << "For map #" << ++map_count << ", the visible buildings are numbered as follows:" << endl; int visible_building_count = 0; for (auto& cur : buildings) for (auto& mx : mx_occur) if (visible(cur, buildings, mx)) { cout << (visible_building_count++ ? " " : "") << cur.id; break; } cout << endl; } return 0; } |
1 |
#TODO |