백준5377 승혁이의 과외돌이네 집 탈출하기

작성일 | In

문제 링크

  • http://icpc.me/5377

문제 출처

  • 2012 BAPC 예선 G번

사용 알고리즘

  • Convex Hull

시간복잡도

  • $O(N \log N)$

풀이

악동들의 위치로 convex hull을 만들었을 때, 시작점이나 도착점이 convex hull 안에 있으면 탈출할 수 없습니다.
그렇지 않은 경우에는 악동들의 위치와 시작점, 도착점을 모두 포함해서 convex hull을 만든 뒤, convex hull의 변을 따라서 이동하는 게 최적이라는 것을 쉽게 알 수 있습니다.

전체 코드

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
istream& operator >> (istream &in, p &t){ in >> t.x >> t.y; return in; }
ostream& operator << (ostream &out, p t){ out << t.x << " " << t.y; return out; }
p operator - (p a, p b){ return p(a.x - b.x, a.y - b.y); }

int n;
vector<p> v;

int ccw(const p &a, const p &b, const p &c){
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    ll res = dx1*dy2 - dx2*dy1;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}
ll dst(const p &a, const p &b){
    ll dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}
int cross(p a, p b, p c, p d){
    int ab = ccw(a, b, c) * ccw(a, b, d);
    int cd = ccw(c, d, a) * ccw(c, d, b);
    if(!ab && !cd){
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);
        return !(b < c || d < a);
    }
    return ab <= 0 && cd <= 0;
}

vector<p> convexHull(){
    vector<p> ret;
    swap(v[0], *min_element(all(v)));
    sort(v.begin()+1, v.end(), [&](const p &a, const p &b){
        auto cw = ccw(v[0], a, b);
        if(cw) return cw > 0;
        return dst(v[0], a) < dst(v[0], b);
    });
    for(const auto &i : v){
        while(ret.size() >= 2 && ccw(ret[ret.size()-2], ret.back(), i) <= 0) ret.pop_back();
        ret.push_back(i);
    }
    return ret;
}

p st, ed;
int valid(p t){
    int flag = 0;
    for(int i=0; i<n; i++){
        int j = i + 1; if(j == n) j = 0;
        if(ccw(v[i], v[j], st) <= 0) flag = 1;
    }
    return flag;
}

int nxt(int x){ return x+1 == n ? 0 : x+1; }
int prv(int x){ return x == 0 ? n-1 : x-1; }

void solve(){
    cin >> st >> ed >> n; v.resize(n); for(auto &i : v) cin >> i;
    v = convexHull(); n = v.size();
    if(!valid(st)){ cout << "IMPOSSIBLE\n"; return; }
    if(!valid(ed)){ cout << "IMPOSSIBLE\n"; return; }
    v.push_back(st); v.push_back(ed);
    v = convexHull(); n = v.size();
    int i, j;
    for(i=1; i<=n&&ccw(v[i-1], v[i%n], st)>0; i++);
    for(j=1; j<=n&&ccw(v[j-1], v[j%n], ed)>0; j++);
    if(i == j || i > n || j > n){ cout << fixed; cout.precision(3); cout << sqrt(dst(st, ed)) << "\n"; return; }
    i %= n; j %= n;
    double t1, t2;
    t1 = sqrt(dst(st, v[i])) + sqrt(dst(ed, v[prv(j)]));
    t2 = sqrt(dst(st, v[prv(i)])) + sqrt(dst(ed, v[j]));
    for(int k=i; k!=prv(j); k=nxt(k)) t1 += sqrt(dst(v[k], v[nxt(k)]));
    for(int k=j; k!=prv(i); k=nxt(k)) t2 += sqrt(dst(v[k], v[nxt(k)]));
    cout << fixed; cout.precision(3); cout << min(t1, t2) << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
}