스카이라인

Problem link: https://www.acmicpc.net/problem/1933

큰 특이 사항이 없는 라인 스위핑 문제이다.

각 건물의 좌우 경계를 opening / closing edge로 나누어 저장하고 x 방향으로 스위핑한다.

조금 까다로운 점은 각 위치에서 가장 높은 edge를 구하기 위한 자료구조를 선정하는 것이 있다.

나의 경우는 <높이, 빌딩번호>를 키로 하는 set을 사용하였다.

어차피 opening edge를 만날 때 삽입될 것이고 closing edge를 만날때 삭제될 것이므로 <높이, 빌딩번호> 키는 유일하게 edge를 식별할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const size_t kMaxN = 100000;

struct Edge
{
  size_t xpos_;
  size_t height_;
  size_t bldg_no_;
  bool is_opening_;

  Edge(const size_t xpos, const size_t height, const size_t bldg_no, const bool is_opening)
    : xpos_(xpos), height_(height), bldg_no_(bldg_no), is_opening_(is_opening)
  {
  }

  bool operator<(const Edge& rhs) const
  {
    return xpos_ < rhs.xpos_;
  }
};

size_t N;
vector<Edge> EDGES;

void Solve(void)
{
  sort(EDGES.begin(), EDGES.end());

  size_t prev_height = 0;
  set<pair<size_t, size_t> > pool;

  size_t edge_no = 0;
  while (edge_no < EDGES.size())
  {
    const auto& edge = EDGES[edge_no];
    if (edge.is_opening_)
    {
      pool.emplace(edge.height_, edge.bldg_no_);
    }
    else
    {
      auto it = pool.find(pair<size_t, size_t>(edge.height_, edge.bldg_no_));
      pool.erase(it);
    }

    if (edge_no + 1 == EDGES.size())
    {
      cout << edge.xpos_ << ' ' << 0 << ' ';
    }
    else if (edge.xpos_ != EDGES[edge_no + 1].xpos_)
    {
      if (pool.empty())
      {
        cout << edge.xpos_ << ' ' << 0 << ' ';
      }
      else
      {
        size_t height = pool.rbegin()->first;
        if (prev_height != height)
        {
          cout << edge.xpos_ << ' ' << height << ' ';
          prev_height = height;
        }
      }
    }

    ++edge_no;
  }

  cout << '\n';
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;

  for (size_t it = 0; it < N; ++it)
  {
    size_t l, h, r;
    cin >> l >> h >> r;
    EDGES.emplace_back(l, h, it, true);
    EDGES.emplace_back(r, h, it, false);
  }

  // Solve
  Solve();

  return 0;
}