BOJ17611: 직각다각형

https://www.acmicpc.net/problem/17611

  • 여러 문제를 푸니까 대부분 비슷한게 느껴진다임
  • 스위핑에서 선분을 다룰때, 겹친 놈들의 개수를 세야 하면 Priority Queue를 쓰면 쉽게 풀린다.
  • 지금까지 본 1차원 유형들
  • 겹친 개수 세기
  • 특정 구간 내 선분의 최대 개수
  • 최소 선분으로 꽉채우기
  • 2차원은 한문제 풀어봤는데, 한쪽 축은 라인스위핑, 한쪽 축은 Fenwick을 쓰는 형태임
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
#include <bits/stdc++.h>
using namespace std;

struct Seg {
  int l, r;
  bool operator<(const Seg &b) {
    return l < b.l;
  }
};

class MaxOverlap {
  vector<Seg> segs;

public:
  void push(int l, int r) {
    if(l > r) swap(l,r);
    segs.push_back({l,r});
  }
  
  int sweep() {
    int ans = 0;
    sort(segs.begin(), segs.end());
    priority_queue<int,vector<int>,greater<int>> pq;
    for(auto [l, r] : segs) {
      pq.push(r);
      while(pq.size() && pq.top() <= l)
        pq.pop();
      ans = max(ans,(int) pq.size());
    }
    return ans;
  }
};

int main() {
  int N, x, y, px, py, fx, fy;
  scanf("%d", &N);
  MaxOverlap mox, moy;
  for(int i = 0; i < N; i++) {
    scanf("%d %d", &x, &y);
    if (!i)
      px = x, py = y, fx = x, fy = y;
    else {
      if (px == x) mox.push(py, y);
      else moy.push(px, x);
      px = x, py = y;
    }
  }
  if (px == fx) mox.push(py, fy);
  else moy.push(px, fx);
  cout << max(mox.sweep(), moy.sweep());
}