백준15939 쉬운 최단경로 문제

작성일 | In

문제 링크

  • http://icpc.me/15939

문제 출처

  • 2018 UCPC B번

풀이

각 쿼리는 주어진 두 점 $p_1, p_2$의 위치에 따라 3가지 경우로 나눌 수 있습니다.

  1. 두 점 모두 다각형 외부에 존재
  2. 두 점 중 한 개가 다각형 외부, 한 개는 내부에 존재
  3. 두 점 모두 다각형 내부에 존재

1번의 답은 0입니다.
2번의 답은 ($p_1$이 다각형 외부로 나가기 위해 지나는 대각선의 개수)입니다.
3번의 답은 min($p_1, p_2$가 모두 다각형 외부로 나가기 위해 지나는 대각선의 개수, $p_1, p_2$를 잇는 선분과 교차하는 대각선의 개수)입니다.

(어떤 점이 다각형 외부로 나가기 위해 지나는 대각선의 개수)와 (두 점을 잇는 선분과 교차하는 대각선의 개수)를 $O(N)$ 정도에 구해야 합니다.


다각형의 꼭짓점에 각각 반시계 방향으로 0부터 N-1까지의 번호를 붙여줍시다.
다각형 내부에 점 p가 주어졌을 때, i번째 꼭짓점에 대해 ccw(i, j, p) > 0인 j의 범위는 [i+1, k] 형태로 표현할 수 있습니다.
k는 단조 증가하기 때문에, 모든 i에 대한 k값을 $O(N)$에 구할 수 있고, 이를 nxt_p[i]라고 정의합시다.


두 점 $p_1, p_2$를 연결하는 선분 $l$과 교차하는 대각선의 개수를 먼저 구해봅시다.
다각형의 $i$번째 꼭짓점에서 출발하는 대각선 중에서 $l$과 교차하는 대각선의 개수는 $\vert nxt_{p_1}[i] - nxt_{p_2}[i] \vert$입니다. 모든 $i$에 대해 저 값을 구해준 뒤 2로 나눠주면 됩니다.


점 $p$에서 다각형 밖으로 나갈 때 지나는 대각선의 개수를 구해봅시다.
점 $p$에서 다각형의 $i, i+1$번째 꼭짓점을 잇는 변을 통해 외부로 나갈 때, 몇 개의 대각선을 지나야 하는지 구하고 그 중 최솟값을 취하면 됩니다.

위 그림의 가장 아래에 있는 점에서 출발하는 대각선들만 고려했을 때, 다각형의 각 변으로 나갈 때 거치는 대각선의 개수를 봅시다.
nxt_p[i] 이후에 있는 각 변에는 +0, +1, +2, …이 더해지고, nxt_p[i] 이전에 있는 각 변에는 +1, +2, +3이 더해집니다. 빨간색 글씨로 되어있는 부분은 수가 1씩 증가하면서 순차적으로 더해지고, 파란색 글씨로 되어있는 부분은 마지막에 더해진 값이 한 번 더 반복됩니다.
빨간색 글씨처럼 구간에 등차수열을 더하는 것은 누적합 배열 2개를 이용해서 처리할 수 있습니다.

모든 꼭짓점에 대해, 각 변으로 나갈 때 거쳐야 하는 대각선의 개수를 구해서 더한 뒤 2로 나눈 값이 우리가 원하는 값이 됩니다.

기하 문제 특성상 한 번에 풀기 어렵습니다. 문제를 풀면서 직접 만든 데이터를 정답 코드 아래에 올렸습니다. 디버깅할 때 유용하게 쓰일 수 있습니다.

전체 코드

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
#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; }

int n, q; p a[10101];
int nxt[2][5050];

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) return 0;
    return res > 0 ? 1 : -1;
}

int out_of_polygon(p pt){
    for(int i=0; i<n; i++) if(ccw(a[i], a[i+1], pt) != 1) return 1;
    return 0;
}

void get_next(int *arr, p pt){
    for(int i=0; i<n; i++){
        arr[i] = arr[i-1];
        if(i == arr[i]%n) arr[i]++;
        while(ccw(a[i], a[arr[i]+1], pt) == 1) arr[i]++;
    }
}

int move_inside(){
    int ret = 0;
    for(int i=0; i<n; i++) ret += abs(nxt[0][i] - nxt[1][i]);
    return ret >> 1;
}

int sum1[10101], sum2[10101];
int move_outside(int *arr){
    memset(sum1, 0, sizeof sum1);
    memset(sum2, 0, sizeof sum2);

    for(int i=0; i<n; i++){ int j = arr[i];
        sum1[i] += j-i-1; sum1[i+1] -= j-i-1;
        sum1[i-1+n] += n+i-j-2; sum1[i+n] -= n+i-j-2;
        sum1[j] -= j; sum1[i-1+n] += j;
        sum2[j]++; sum2[i-1+n]--;
        sum1[i+1] += j; sum1[j] -= j;
        sum2[i+1]--; sum2[j]++;
    }
    for(int i=1; i<n+n; i++) sum1[i] += sum1[i-1], sum2[i] += sum2[i-1];
    int ret = 1e9;
    for(int i=0; i<n; i++){
        int now = sum1[i] + i*sum2[i];
        now += sum1[i+n] + (i+n)*sum2[i+n];
        ret = min(ret, now);
    }
    return (ret >> 1) + 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i], a[i+n] = a[i];
    cin >> q;
    while(q--){
        p p1, p2; cin >> p1 >> p2;
        int out1 = out_of_polygon(p1), t1 = 0;
        int out2 = out_of_polygon(p2), t2 = 0;
        if(out1 && out2){ cout << "0\n"; continue; }
        if(out1 && !out2){ swap(p1, p2); swap(out1, out2); } // p1 -> always inside
        if(!out1) get_next(nxt[0], p1), t1 = move_outside(nxt[0]);
        if(!out2) get_next(nxt[1], p2), t2 = move_outside(nxt[1]);

        if(!out1 && out2) cout << t1 << "\n";
        else cout << min(move_inside(), t1+t2) << "\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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
6
-5 -5
5 -4
6 1
2 4
-3 5
-6 0
1
0 1 -10 -10

정답: 4

4
-5 -5
5 -5
5 5
-5 5
1
-10 -10 0 2

정답: 1

5
-2 -5
3 -4
6 0
0 5
-4 2
2
0 0 -100 0
3 -1 -100 0

정답: 3 2

6
-5 -5
5 -5
7 0
5 5
-5 5
-7 0
1
-6 1 6 1

정답: 2