백준10839 미술관

작성일 | In

문제 링크

  • http://icpc.me/10839

문제 출처

  • 2015 KOI 중등부 4번

사용 알고리즘

  • Convex Hull

시간복잡도

  • $O(N log N)$

풀이

문제에서 두 정점 사이의 최단 경로는 항상 다각형의 꼭짓점에서만 꺾인다고 주어져있습니다. 이 점에 유의해서 풀이를 생각해봅시다.


문제에서 주어진 이 그림에서 v4부터 v11까지 가는 최단 경로를 찾아봅시다.
다각형의 꼭짓점에서만 경로가 꺾이기 때문에, 변을 하나씩 따라가면서 손해가 되는 변들을 제거하는 형태로 경로를 찾을 것입니다.



v6까지는 변을 그대로 타고 가는 것이 최단 경로입니다. v7로 가는 길을 한 번 봅시다.


빨간색 경로로 가는 것보다는 초록색 경로로 가는 것이 더 짧습니다. (v5, v6), (v6, v7)을 잇는 변 대신 (v5, v7)을 잇는 대각선을 통해 이동합시다.


(v5, v7)을 잇는 대각선과 (v7, v8)을 잇는 대각선은 평행합니다. 이런 경우에도 경로 상에서 v7을 지워주고 (v5, v8)을 잇는 대각선을 통해 이동합시다.


빨간색 경로로 가는 것보다는 초록색 경로로 가는 것이 더 짧기 때문에 (v5, v9)를 잇는 대각선을 통해 이동합시다.

우리는 이런 결과를 얻을 수 있습니다.

빨간색 경로를 지우고 초록색 경로를 넣는 상황이 발생하는 경우는 시점은 좌회전을 하는 시점과 동일합니다. 우리는 이때 좌회전이 없어질 때까지 기존 경로를 하나씩 제거한 다음에 새로운 경로를 추가합니다. 결국, Convex Hull을 구하는 작업을 한 것입니다.
a < b일때 va에서 vb까지 가는 답을 구하는 것은 a번째부터 b번째까지의 점을 이용하여 convex hull을 구하는 것으로 해결할 수 있으며, graham scan을 해주면 됩니다.
a > b인 경우에는 vb에서 va까지 가는 경로를 구한 다음 뒤집어주면 됩니다.

v0에서 시작할 때 답을 잘못 구하는 경우가 생길 수 있습니다. 이런 경우에는 vn = v0인 vn을 추가해서 vn까지 가는 경로를 구해주는 것으로 해결할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n;
p arr[201010];

int ccw(p a, p b, p c){
    ll res = a.x*b.y + b.x*c.y + c.x*a.y;
    res -= b.x*a.y + c.x*b.y + a.x*c.y;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}
inline int ccw(int a, int b, int c){ return ccw(arr[a], arr[b], arr[c]); }

vector<int> go(int s, int e){
    if(s == e) return vector<int>(s, 0);
    if(s+1 == e) return {s, e};
    vector<int> ret;
    if(s == 0){
        ret = go(e, n);
        ret.back() -= n;
        return ret;
    }
    ret.push_back(s);
    for(int i=s+1; i<=e; i++){
        while(ret.size() >= 2 && ccw(ret[ret.size()-2], ret.back(), i) >= 0) ret.pop_back();
        ret.push_back(i);
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i].x >> arr[i].y; arr[n] = arr[0];
    int st, ed; cin >> st >> ed;
    auto ans = go(min(st, ed), max(st, ed));
    if(ans[0] == ed) reverse(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for(auto i : ans) cout << i << " ";
}