KOI 2019 1차 중등부 2번 / 직각다각형 - 17611

#include <iostream>
#include <queue>
using namespace std;
 
int N;
 
struct Node {
    int idx;
    char label;
};
 
bool operator<(const Node& n1, const Node& n2) {
    if(n1.idx == n2.idx) return n1.label < n2.label;
    return n1.idx < n2.idx;
}
 
priority_queue<Node> pq[2];
 
void mkpq(int u1, int u2, int v1, int v2) {
    Node x1, x2, y1, y2;
    x1.label = y1.label = 's';
    x2.label = y2.label = 'e';
 
    x1.idx = max(u1, u2);
    x2.idx = min(u1, u2);
    y1.idx = max(v1, v2);
    y2.idx = min(v1, v2);
    pq[0].push(x1); pq[0].push(x2);
    pq[1].push(y1); pq[1].push(y2);
}
 
int Cnt(priority_queue<Node>& pq) {
    int ret = 0;
    int cnt = 0;
 
    int bidx = -1000000;
    while(!pq.empty()) {
        Node n = pq.top();
        pq.pop();
        if(bidx == n.idx) {
            if(n.label == 's') ++cnt;
            else --cnt;
        }
        else {
            ret = max(ret, cnt);
            bidx = n.idx;
            ++cnt;
        }
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    int u, v, su, sv, bu, bv;
    cin >> su >> sv;
    bu = su, bv = sv;
    for(int i = 0; i<N-1; ++i) {
        cin >> u >> v;
        mkpq(u, bu, v, bv);
        bu = u, bv = v;
    }
    mkpq(u, su, v, sv);
    int ans = 0;
    ans = max(ans, Cnt(pq[0]));
    ans = max(ans, Cnt(pq[1]));
    cout << ans;
}

 

 

 

 

 

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

17611번: 직각다각형

 

 

 

 

 

직각다각형

세로축에 평행한 선분들을 추출해서 가장 많이 겹치는 곳이 몇번 겹치는지 세고,

가로축에 평행한 선분들을 추출해서 가장 많이 겹치는 곳이 몇번 겹치는지 세어서

그중 가장 많이 겹치는 것을 정답으로 출력 하면 됩니다.

lazy propagation을 사용해도 되지만, 사실 각각 선분의 꼭지점이 시작점인지 끝점인지만 구분해서 시작점이면 ++cnt, 끝점이면 --cnt를 해준다면 더 쉽게 셀 수 있습니다.

문제의 조건에서 수평선 H, V는 어떤 선분과도 겹치면 안된다는 성질만 조심하면 쉽게 해결 할 수 있습니다.