首页 > 代码库 > UVa221 Urban Elevations
UVa221 Urban Elevations
离散化处理。判断建筑可见性比较麻烦。下面采用离散化解决:把所有的x坐标排序去重,在相邻两个x坐标表示的区间中,整个区间要么同时可见,要么同时不可见。如何判断该区间是否可见?具体做法是选取该区间中点坐标x=mx来做代表,判断mx是否可见。那么判断该监周屋是否在点mx0可见?首先该建筑物必须包含该点,并且在他南边的包含该点的建筑物不能比它高。
//--------离散化处理技巧//----------------------#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<vector>#include<algorithm>#include<cmath>using namespace std;const int maxn = 100+ 5;struct Building{ int id; double x, y, w, l, h; bool operator<(Building m){ if (m.x == x)return y < m.y; else return x < m.x; }} b[maxn];double x[2 * maxn];int n,m;//判断下标为i的建筑物在x=mx处是否覆盖bool cover(int i, double mx){ return mx<b[i].x + b[i].w&&mx>b[i].x;}//判断建筑物是否在mx处可见bool isVision(int i, double mx){ if (!cover(i, mx))return false; //判断它南边是否有建筑物覆盖该点 for (int k = 0; k < n; k++){ if (b[k].y<b[i].y&&b[k].h>=b[i].h&&cover(k, mx)) return false; } return true;}int main(){ int kase = 1; while (scanf("%d", &n) && n){ for (int i = 0; i < n; i++){ scanf("%lf%lf%lf%lf%lf",&b[i].x, &b[i].y, &b[i].w, &b[i].l, &b[i].h); b[i].id = i + 1; x[2 * i] = b[i].x, x[2 * i + 1] = b[i].x + b[i].w; } sort(b, b + n); sort(x, x + 2 * n); //去重复 m = unique(x, x + 2*n) - x; vector<int>v; int j; for (int i = 0; i < n; i++){ //枚举每一个mx for (j = 0; j < m - 1; j++){ if (isVision(i, (x[j] + x[j + 1]) / 2)) break; //一旦遇到当前建筑物在该点可见则跳出循环 } if (j<m-1)v.push_back(b[i].id); } if (kase>1)printf("\n"); printf("For map #%d, the visible buildings are numbered as follows:\n", kase++); printf("%d", v[0]); for (int i = 1; i < v.size(); i++)printf(" %d", v[i]); printf("\n"); } return 0;}
UVa221 Urban Elevations
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。