https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=157
题意:输入建筑物的x,y坐标,宽度,深度和高度,输出从南向北看时能看到的建筑物。
这道题需要用到离散化,将所有建筑物物的左右边界坐标存储起来,然后排序去重,那么任意两个相邻x坐标形成的区间要么是可见的,要么就是不可见的。这样只需在这个区间内任选一点(如中点),当该建筑物可见时,首先它的左右边界必须包含这个中点,其次,在它前面不能有比它高的建筑物。
在排序去重时需要用到unique函数,它是c++中的去重函数,但是它不会删除那些重复的函数,而是把它们移到了数组的最后,当需要获得该数组中不重复元素的个数,则是这样的形式unique(x, x + 2*n) - x
1 #include<iostream>
2 #include<algorithm>
3 #include<string>
4 #include<cstring>
5 using namespace std;
6
7 const int maxn = 105;
8
9 struct Building{
10 int id;
11 double x, y, w, d, h;
12 bool operator < (const Building& rhs) const{
13 return x < rhs.x || (x == rhs.x && y < rhs.y); //重载<运算符
14 }
15 }b[maxn];
16
17 int n;
18 double x[2*maxn];
19
20 bool solve(int i, double mi)
21 {
22 if(!(b[i].x<=mi && b[i].x + b[i].w>=mi)) return false; //该中点不在建筑物b[i]范围内时返回false
23 for(int k = 0; k < n;k++)
24 {
25 if (b[k].y<b[i].y && b[k].h >= b[i].h && b[k].x <= mi && b[k].x + b[k].w >= mi) return false;
26 //若该建筑物前面有建筑物并且高度大于等于该建筑物时,返回false
27 }
28 return true;
29 }
30
31 int main()
32 {
33 int kase = 0;
34 while (cin >> n, n)
35 {
36 memset(x, 0, sizeof(x));
37 for (int i = 0; i < n; i++)
38 {
39 cin >> b[i].x >> b[i].y >> b[i].w >> b[i].d >> b[i].h;
40 b[i].id = i + 1;
41 x[2 * i] = b[i].x;
42 x[2 * i + 1] = b[i].x + b[i].w;
43 }
44 sort(b, b + n); //以重载方法进行排序
45 sort(x, x + 2 * n);
46 int m = unique(x, x + 2*n) - x; //得到不重复的x坐标个数
47 if(kase++) cout << endl;
48 cout << "For map #" << kase << ", the visible buildings are numbered as follows:" << endl << b[0].id;
49 for (int i = 1; i < n; i++)
50 {
51 bool vis = false;
52 for (int j = 0; j < m; j++)
53 {
54 if (solve(i, (x[j] + x[j + 1]) / 2)) { vis = true; break; }
55 }
56 if (vis == true) cout << " " << b[i].id;
57 }
58 cout << endl;
59 }
60 return 0;
61 }
原文链接: https://www.cnblogs.com/zyb993963526/p/6233353.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/246729
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!