UVaOJ 221 - Urban Elevations

问题描述

解法一：排序 + 离散化

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

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ