BOJ)5849 Cow Crossings

문제: icpc.me/5849

N개의 2점이 주어진다.

a[i]와 b[i]인데 이 문제는 각 (a[i],0)과 (b[i],1) 두 점을 잇는 N가지 직선들 중 다른 어떤 직선과도 겹치지 않는 직선의 수를 세는 문제이다.

N^2으로 완전 탐색을 하는 방법으로는 해결이 불가능하니, 보통 이러한 류의 문제에서는 스위핑을 이용하게 되는데

우선 a[i]를 기준으로 정렬을 해보자.

그러고 a[i]가 증가하는 순서대로 보면 이러한 생각을 하게 될 수 있다.

내가 이전에 본 직선들의 b[x]의 좌표 중에 나의 b[i]보다 하나라도 큰 수가 있다면 나는 이전에 업데이트 된 직선에 의해서 겹치는 직선이 된다는 걸 알 수 있다.

이러한 원리로 우선 a[i]가 증가되는 순서로 안되는 직선들을 걸러준다.

하지만 이렇게 처리하면 몇가지 직선이 처리가 안된다. 그 직선들은 반대로 a[i]가 감소하는 순서대로 보면서 

이전에 본 b[x]의 좌표중에서 나의 b[i]보다 하나라도 작은 수가 있다면 겹치는 직선이 됨을 이용해 지워준다.

안되는 모든 직선들을 구해준 뒤 n에서 수를 빼주면 답을 구할 수 있다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, cant[100020];
pair<int, int> a[100020];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &a[i].first, &a[i].second);
    priority_queue<int> pq;
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        int curr = a[i].second;
        if (pq.size() && pq.top()>curr)
            cant[i] = 1;
        pq.push(curr);
    }
    priority_queue<int> qp;
    for (int i = n - 1; i >= 0; i--) {
        int curr = a[i].second;
        if (qp.size() && -qp.top() < curr)
            cant[i] = 1;
        qp.push(-curr);
    }
    int res = n;
    for (int i = 0; i < n; i++)
        if (cant[i])res--;
    printf("%d\n", res);
    return 0;
}