例题5-12 城市正视图（Urban Elevations，ACM/ICPC World Finals 1992，UVa221）

本文主要是介绍例题5-12 城市正视图（Urban Elevations，ACM/ICPC World Finals 1992，UVa221），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-221
分类：<algorithm>
备注：离散化
前言：我也不太清楚刘老师为什么说这题是离散化，我想可能是用到集合的东西吧，区间完全包含于建筑的区间或者交集为空，这都是离散的知识。
但是把无限变为有限是很有用的一种思想！
本题我确实借鉴了VJ中Praying的评论中的代码，所以会很像！

代码如下：

#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100 + 5;
int n, kase;
struct CBuild {double x, y, xw, yw, h;int xb;bool operator < (const CBuild& t) const {if (x != t.x)return x < t.x;return y < t.y;}
}b[maxn];
bool vis(int k) {double l = b[k].x, r = b[k].x + b[k].xw;set<CBuild>tmp;for (int i = 0; i < n; i++) {//找到所有遮挡建筑if (b[i].x >= r || b[i].x + b[i].xw <= l)continue;if (b[i].y >= b[k].y || b[i].h < b[k].h)continue;tmp.insert(b[i]);}if (tmp.empty())return true;set<CBuild>::iterator it = tmp.begin();if (l < (*it).x)return true;//最左边漏出double r2 = (*it).x + (*it).xw;it++;for (; it != tmp.end(); it++) {if ((*it).x > r2)return true;//找到中间的空，中间漏出r2 = max(r2, (*it).x + (*it).xw);//从最左边到r2处是目前找到的最长连续段}if (r > r2)return true;//最右边漏出return false;
}
int main(void) {while (~scanf("%d", &n) && n) {if (kase)printf("\n");set<CBuild>ans;for (int i = 0; i < n; i++) {scanf("%lf%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].xw, &b[i].yw, &b[i].h);b[i].xb = i + 1;}sort(b, b + n);for (int i = 0; i < n; i++) if (vis(i))ans.insert(b[i]);printf("For map #%d, the visible buildings are numbered as follows:\n", ++kase);for (set<CBuild>::iterator it2 = ans.begin(); it2 != ans.end(); ++it2) {if (it2 != ans.begin())printf(" ");printf("%d", (*it2).xb);}printf("\n");}return 0;
}