MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 221 - Urban Elevations
AOAPC II

UVaOJ 221 - Urban Elevations

Chai
2021-11-24 0:00:00在线评测阅读 442

问题描述

p221

原题链接:UVaOJ 221 - Urban Elevations

相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-12

解法一:排序 + 离散化

题目要求输出需要按照自定义顺序排序,因此自定义 Building 结构体时重载一下 < 运算符,接下来就可以遍历处理,关键在于如何判断当前的建筑物是否可见 —— 由于观察视角是正前方,因此可以根据东西方向的 x 轴进行离散化采样,得到用于判断的所有可能坐标 mx (因为所有出现的 x 与 x+w 坐标是已知的,我们只需要把这个方向的所有坐标整理出来,对于每个单独的区间去判断当前建筑物是否可见即可, mx 可以随机从每个区间中取,最简单的做法就是取中点)。对于给定的 mx ,想要判断某个建筑在这个位置是否可见,只需要验证是否有其它建筑物进行了遮挡即可,遮挡的条件是:1. 位置比当前建筑物更靠近南方向;2. 高度比当前建筑物高。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
 
using namespace std;
 
struct Building {
  int id;
  double x, y, w, d, h;
  bool operator<(const Building& rhs) const {
    return (x < rhs.x) || (x == rhs.x && y < rhs.y);
  }
  bool cover(const double mx) const { return (x <= mx) && (x + w >= mx); }
  bool behind(const Building& rhs) const { return (rhs.y < y) && (rhs.h >= h); }
};
 
bool visible(const Building& cur, const vector<Building>& building, double mx) {
  if (!cur.cover(mx)) return false;
  for (auto& b : building)  // check if any building is behind
    if (cur.behind(b) && b.cover(mx)) return false;
  return true;
}
 
int main() {
  int map_count = 0, building_count = 0;
  while (cin >> building_count && building_count) {
    vector<Building> buildings;
    set<double> x_coord;
    for (int id = 1; id <= building_count; ++id) {
      double x, y, w, d, h;
      cin >> x >> y >> w >> d >> h;
      buildings.push_back({id, x, y, w, d, h});  // id is 1-based
      x_coord.insert({x, x + w});
    }
    sort(buildings.begin(), buildings.end());  // for output in order
 
    vector<double> x_occur(x_coord.begin(), x_coord.end());
    vector<double> mx_occur;
    for (int i = 0; i < x_occur.size() - 1; ++i)
      mx_occur.push_back((x_occur[i] + x_occur[i + 1]) / 2);
 
    cout << (map_count ? "\n" : "") << "For map #" << ++map_count
         << ", the visible buildings are numbered as follows:" << endl;
 
    int visible_building_count = 0;
    for (auto& cur : buildings)
      for (auto& mx : mx_occur)
        if (visible(cur, buildings, mx)) {
          cout << (visible_building_count++ ? " " : "") << cur.id;
          break;
        }
    cout << endl;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz