백준19650 개미여행

작성일 | In

문제 링크

  • http://icpc.me/19650

사용 알고리즘

  • 기하
  • 플로이드

시간복잡도

  • $O(N^3)$

풀이

그래프를 잘 만들고 최단 거리를 구하면 됩니다!
그래프를 만드는 난이도가 Diamond3인 것이 문제입니다.

어떤 점 X가 K개의 점 중 3개를 골라서 만든 삼각형 내부에 속하지 않는다.는 점 K개로 만든 볼록 껍질 안에 점 X가 속하지 않는다는 것을 의미합니다. 각 개미 그룹에 대해 Convex Hull을 만들어줍시다.

Convex Hull의 꼭짓점과 시작점, 끝점을 통해서만 이동해도 최단 경로를 찾을 수 있는 것은 직관적으로 알 수 있습니다. 두 점 $u, v$ 사이를 이동할 수 있는지, 즉 두 정점 $u, v$를 잇는 간선을 만들어도 되는지 판별하는 것이 이 문제의 핵심입니다.

$u, v$를 잇는 선분의 일부가 어떤 Convex Hull의 내부(경계 제외)에 들어가 있다면 이동할 수 없습니다. 그렇지 않은 경우에는 이동할 수 있습니다. 조금 더 상세하게 케이스를 분류하면 다음과 같습니다.

  1. 선분의 양 끝점 중 하나 이상이 Convex Hull 내부에 있음
  2. 두 선분이 평행하지 않고, 끝점이 아닌 지점에서 교차
  3. 선분의 중점이 Convex Hull 내부에 있음

1번 케이스는 단순히 $O(N)$ Point in Polygon을 구현해주면 됩니다.
2번 케이스는 선분 교차 여부를 묻는 경우이고, ccw 4번으로 구현할 수 있습니다.
3번 케이스는 중점 뿐만 아니라 임의의 내분점을 사용해도 무방하지만, 중점을 사용하는 것이 정신 건강에 좋습니다. 반정수는 부동소수점으로 정확하게 표현할 수 있긴 하지만, 기하 라이브러리를 정수/실수로 두 번 구현하기는 귀찮으므로 좌표 범위를 2배로 늘려서 구현합시다.

위 과정을 잘 구현하고 Floyad-Warshall이나 Dijkstra를 추가해서 제출하면 8x%에서 WA를 받습니다.


위 그림에서 초록색 경로가 최적이지만 보라색 경로로 갈 수 있다고 판별하는 것이 문제입니다. 가운데 있는 점이 시작점과 끝점을 잇는 선분의 중점인데, 어떠한 Convex Hull 내부에도 속하지 않기 때문에 생기는 문제입니다.
2등분, 3등분, …, X등분해서 여러 점에 대해 판별해주면 사실상 막는 것은 불가능하지만 이는 대회에서 최후의 경우에 쓰는 방법이고, 이건 대회가 아니니까 제대로된 풀이를 찾아서 푸는 것이 좋습니다.


위에서 본 저격 데이터가 문제가 되는 경우는 이 그림처럼 두 점을 잇는 선분 위에 다른 점이 존재하는 경우입니다. 이런 경우를 피하기만 하면 됩니다.
검은색으로 표시된 경로를 만들지 않아도 연두색과 분홍색으로 표시된 경로 두 개로 검은색을 표현할 수 있습니다. 그러므로 두 점을 잇는 선분 위에 다른 점이 존재한다면 굳이 그 선분을 만들지 않아도 됩니다.

이 부분까지 구현해주면 AC를 받을 수 있습니다.

전체 코드

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#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())
#define SZ(v) int(v.size())
using namespace std;

typedef long long ll;
typedef long double ld;

struct p{
    ll x, y; int idx, gid; // 좌표, 개미 번호, 그룹 번호
    p() : p(0, 0) {}
    p(ll x, ll y) : x(x), y(y), idx(-917), gid(-917) {}
    p operator * (ll t){ return p(x*t, y*t); }
    bool operator == (const p &t) const { return tie(x, y) == tie(t.x, t.y); }
    bool operator < (const p &t) const { return tie(x, y) < tie(t.x, t.y); }
    bool operator <= (const p &t) const { return *this < t || *this == t; }
};
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; }
int ccw(const p &a, const p &b, const p &c){
    ll res = (b.x-a.x) * (c.y-b.y) - (c.x-b.x) * (b.y-a.y);
    if(!res) return 0;
    return res > 0 ? 1 : -1;
}
ll D(const p &a, const p &b){
    ll dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}
ld dst(const p &a, const p &b){ return sqrt((ld)D(a, b)); }
vector<p> convex_hull(vector<p> &v){
    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 D(v[0], a) < D(v[0], b);
    });
    for(const auto &i : v){
        while(SZ(ret) >= 2 && ccw(ret[SZ(ret)-2], ret.back(), i) <= 0) ret.pop_back();
        ret.push_back(i);
    }
    return ret;
}
int cross(p a, p b, p c, p d){ // 두 선분 ab와 cd가 끝점이 아닌 지점에서 만나는지 판별
    int ab = ccw(a, b, c) * ccw(a, b, d);
    int cd = ccw(c, d, a) * ccw(c, d, b);
    return ab < 0 && cd < 0;
}
int pip(const vector<p> &v, p pt){ // pt가 convex hull 안에 속하는지 판별
    for(int i=0; i<SZ(v); i++){
        if(ccw(v[i], v[(i+1)%SZ(v)], pt) != 1) return 0;
    }
    return 1;
}
int pip_mid(const vector<p> &v, p p1, p p2){ // 선분 p1-p2의 중점이 convex hull 안에 속하는지 판별
    ll xx = p1.x + p2.x, yy = p1.y + p2.y;
    p pt(xx, yy);
    for(int i=0; i<SZ(v); i++){
        int j = (i + 1) % SZ(v);
        p pt1(v[i].x*2, v[i].y*2);
        p pt2(v[j].x*2, v[j].y*2);
        if(ccw(pt1, pt2, pt) != 1) return 0;
    }
    return 1;
}

int n, pv; p s, e, a[111];
vector<p> v[111];
ld w[111][111];

int able(int t1, int t2){ // t1번째 점에서 t2번째 점으로 갈 수 있는지 판별
    if(t1 == t2) return 0;
    int gid = a[t1].gid == a[t2].gid ? a[t1].gid : -1;
    if(gid >= 0){
        if(abs(a[t1].idx - a[t2].idx) <= 1);
        else if(a[t1] == v[gid].front() && a[t2] == v[gid].back());
        else if(a[t2] == v[gid].front() && a[t1] == v[gid].back());
        else return 0;
    }

    for(int i=1; i<=n; i++) if(SZ(v[i]) >= 3){
        if(pip(v[i], a[t1]) || pip(v[i], a[t2])) return 0;
        if(pip_mid(v[i], a[t1], a[t2])) return 0;
    }

    for(int i=1; i<=n; i++) if(SZ(v[i]) >= 3){
        for(int j=0; j<SZ(v[i]); j++){
            int k = (j+1)%SZ(v[i]);
            ll dx1 = a[t1].x - a[t2].x, dy1 = a[t1].y - a[t2].y;
            ll dx2 = v[i][j].x - v[i][k].x, dy2 = v[i][j].y - v[i][k].y;
            if(dx1 * dy2 == dx2 * dy1) continue;
            if(cross(a[t1], a[t2], v[i][j], v[i][k])) return 0;
        }
    }

    auto mn = min(a[t1], a[t2]), mx = max(a[t1], a[t2]);
    for(int i=0; i<=pv; i++) if(i != t1 && i != t2){
        if(mn <= a[i] && a[i] <= mx && !ccw(mn, mx, a[i])) return 0;
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> s >> e >> n;
    for(int i=1; i<=n; i++){
        int m; cin >> m; v[i].resize(m);
        for(auto &j : v[i]) cin >> j;
        if(SZ(v[i]) >= 3) v[i] = convex_hull(v[i]);
        for(auto &j : v[i]) j.gid = i, j.idx = ++pv, a[pv] = j;
    }
    s.gid = 0; s.idx = 0; a[0] = s;
    e.gid = n+1; e.idx = ++pv; a[pv] = e;

    for(int i=0; i<=pv; i++) for(int j=0; j<=pv; j++) w[i][j] = -1e18;
    for(int i=0; i<=pv; i++) w[i][i] = 0;

    for(int i=0; i<=pv; i++) for(int j=0; j<=pv; j++){
        if(!able(i, j)) continue;
        if(w[i][j] < 0) w[i][j] = dst(a[i], a[j]);
        else w[i][j] = min(w[i][j], dst(a[i], a[j]));
    }

    for(int k=0; k<=pv; k++) for(int i=0; i<=pv; i++) for(int j=0; j<=pv; j++){
        if(w[i][k] < 0 || w[k][j] < 0) continue;
        if(w[i][j] < 0) w[i][j] = w[i][k] + w[k][j];
        else w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
    }
    if(w[0][pv] < 0) cout << -1;
    else cout << fixed << setprecision(20) << w[0][pv];
}