티스토리 뷰

알고리즘 관련/BOJ

BOJ)5849 Cow Crossings

JASON 자손9319 2017. 10. 24. 16:14

문제: 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에서 수를 빼주면 답을 구할 수 있다.

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
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, cant[100020];
pair<intint> 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14748 Flow Graph Complexity  (0) 2017.10.24
BOJ)5846 Tractor  (0) 2017.10.24
BOJ)5849 Cow Crossings  (0) 2017.10.24
BOJ)2023 신기한 소수  (0) 2017.10.16
BOJ)13212 Random  (0) 2017.10.16
BOJ)13213 Binary Roads  (0) 2017.10.16
댓글
댓글쓰기 폼