Urban Elevations UVA - 221—

本文主要是介绍Urban Elevations UVA - 221——个人见解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

An elevation of a collection of buildings is an orthogonal projection of the buildings onto a vertical
plane. An external elevation of a city would show the skyline and the faces of the “visible” buildings of
the city as viewed from outside the city from a certain direction. A southern elevation shows no sides;
it shows the perfectly rectangular faces of buildings or parts of faces of buildings not obstructed on the
south by taller buildings. For this problem, you must write a program that determines which buildings
of a city are visible in a southern elevation.
For simplicity, assume all the buildings for the elevation are perfect rectangular solids, each with
two sides that run directly east-west and two running directly north-south. Your program will find the
buildings that appear in a southern elevation based on knowing the positions and heights of each city
building. That data can be illustrated by a map of the city as in the diagram on the left below. The
southern elevation for that city is illustrated in the diagram on the right.

City map. Boldface numbers (in the upper left of each building) identify the buildings. Plain numbers (lower right) are the buildings heights.
Southern Elevation（Only the shaded buildings are visible in a southernelevation)

Input
Input for your program consists of the numeric description of maps of several cities. The first line of
each map contains the number of buildings in the city (a non-negative integer less than 101). Each
subsequent line of a map contains data for a single building — 5 real numbers separated by spaces in
the following order:

x-coordinate of the southwest corner
y-coordinate of the southwest corner
width of the building (length of the south side)
depth of the building (length of the west side)
height of the building

Each map is oriented on a rectangular coordinate system so that the positive x-axis points east and
the positive y-axis points north. Assume that all input for each map corresponds to a legitimate map
(the number of buildings is the same as the number of subsequent lines of input for the map; no two
buildings in a single map overlap). Input is terminated by the number 0 representing a map with no
buildings.

Output
Buildings are numbered according to where their data lines appear in the map’s input data — building
1 corresponding to the first line of building data, building #2 data to the next line, and building
n to the nth line of building data for that map. (Buildings on subsequent maps also begin their
numbering with 1.)
For each map, output begins with line identifying the map (map #1, map #2, etc.) On the next line
the numbers of the visible buildings as they appear in the southern elevation, ordered south-to-north,
west-to-east. This means that if building n and building m are visible buildings and if the southwest
corner of building n is west of the southwest corner of building m, then number n is printed before
number m. If building n and building m have the same x-coordinate for their southwest corners and if
building n is south of building m, then the number n is printed before the number m.
For this program, a building is considered visible whenever the part of its southern face that appears
in the elevation has strictly positive area. One blank line must separate output from consecutive input
records.

Sample Input
14
160 0 30 60 30
125 0 32 28 60
95 0 27 28 40
70 35 19 55 90
0 0 60 35 80
0 40 29 20 60
35 40 25 45 80
0 67 25 20 50
0 92 90 20 80
95 38 55 12 50
95 60 60 13 30
95 80 45 25 50
165 65 15 15 25
165 85 10 15 35
0
Sample Output
For map #1, the visible buildings are numbered as follows:
5 9 4 3 10 2 1 14

题目的意思是给出x、y坐标、东西方向的宽度w、深度d（南北方向）、还有建筑的高度h。让你判断从正南方向看去的试图中所有可以被看到的建筑编号，按x坐标从小到大输出可视建筑的id。

搞明白题目意思就好办了。最主要的难点是怎么判断一个建筑是否可见。（提示：这里用不上深度d,因为是从正南看的，在脑子想象一下实际情况就知道为什么用不上d了）

判断建筑是否可见，根据大神刘汝佳给的方法，可以这么搞：

把x坐标排序，并用unique函数去除重复的坐标，使任意两个相邻的x坐标形成的区间（这里指的是数学意义上的区间）具有相同的属性，而一个区间要么完全可见，要么完全不可见。这样，就只需要在区间里随便选一个点（这里选中点），然后判断建筑是否包含这个点。即如果一个建筑在某个区间可见，则这个建筑包含这个区间选定的某个点的x坐标，且在这个建筑的南边没有比它高的建筑。
下面是AC代码：

#include <iostream>
#include <algorithm>
/**
*编译环境：CodeBlocks 16.01 mingw32-g++.exe -Wall -fexceptions -g -std=c++11
*C++11标准
*/
using namespace std;const int MAX = 105;struct Building  //定义一个建筑类型的数据结构
{int id;double x, y, w, d, h; //(x,y)是一个坐标, w->width, d->deep, h-> heightbool operator < (const struct Building& rhs) const //重载自己的比较运算符{if (x == rhs.x) return y < rhs.y;return x < rhs.x;}
};struct Building b[MAX];
double coordinate[2*MAX]; //用来存放要枚举判断是否符合题意（即是否被覆盖）的坐标
int n {0};bool Cover(int i, double xpoint) //传入一个下标和一个x坐标（因为只需要比较南墙，所以传x坐标比较就够了）
{return b[i].x <= xpoint && b[i].x+b[i].w >= xpoint;//满足这两个条件，说明传入的x坐标被这个下标为i的建筑覆盖了（咳咳，说人话就是这个点在这个建筑（长方形）内）
}bool Visible(int i, double xpoint)
{if (!Cover(i,xpoint)) return false;//被覆盖了就不可见了for (int j=0; j < n; j++)if (b[j].y < b[i].y && b[j].h >= b[i].h && Cover(j,xpoint))//再判断有没有被靠近南面的建筑挡住return false;return true;
}int main()
{int kase{0};while (cin >> n && n){for (int i=0; i < n; i++){cin >> b[i].x >> b[i].y >> b[i].w >> b[i].d >> b[i].h;b[i].id = i+1;coordinate[2*i] = b[i].x;//这算是个小技巧了，只用一个for就可以同时录入两组需要用到的数据coordinate[2*i+1] = b[i].x + b[i].w;}sort(b, b+n);sort(coordinate, coordinate+2*n);//分别排序后去掉重复的坐标int m = unique(coordinate, coordinate+2*n) - coordinate;//unique函数将数组中重复的元素移动到数组末尾，并返回的是一个地址，这个地址前的元素都是不重复的//所以要减去首地址，就得到了不重复的坐标的个数if (kase++)cout<<endl;cout << "For map #" << kase << ", the visible buildings are numbered as follows:\n" << b[0].id;for (int j = 1; j < n; j++) {bool visied = false;for (int k = 0; k < m-1; k++)//枚举判断某个点是否在整个区间内可见（这里取的是中点）if (Visible(j, (coordinate[k] + coordinate[k+1])/2)) {visied = true;break;}if (visied) cout << " " << b[j].id;}cout << endl;}return 0;
}