首页 > 代码库 > 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