[Algorithm] C++ 백준 15939번 쉬운 최단경로

개요

문제: BOJ 15939 쉬운 최단경로 (UCPC 2018 본선 B)
아이디어 요약:
- 두 점의 위치에 따라 세 경우로 분기
  1. 두 점 모두 다각형 외부: 답 0
  2. 한 점만 내부: 내부 점이 밖으로 나갈 때 지나야 하는 대각선 최소 개수
  3. 두 점 모두 내부: 다음 두 값의 최솟값
    - 두 점을 잇는 선분과 교차하는 대각선의 개수
    - 각 점이 외부로 나갈 때 지나야 하는 대각선 최소 개수의 합
복잡도: 쿼리당 O(N). 내부/외부 판정은 O(log N)로 최적화해 상수 시간을 줄임.

풀이 메모

다각형은 반시계(CCW) 볼록다각형.
내부 점 p에 대해 각 정점 i에서 p 기준 왼쪽이 되는 최대 j를 투포인터로 O(N)에 구해 nextIdx[i]로 저장.
내부→외부 최소 비용은 각 변을 통해 나가는 경우를 누적합 2개(차분 배열)로 한 번에 계산해 최솟값을 취함.
두 내부 점의 직선 교차 대각선 수는 sum_i |nxt1[i] - nxt2[i]| / 2.

구현 (C++)

  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
135
136
137
138
139
140
141
142
143
144
// 더 많은 정보는 42jerrykim.github.io에서 확인할 수 있습니다: https://42jerrykim.github.io
#include <bits/stdc++.h>
using namespace std;

struct Point { long long x, y; };

static inline long long cross(const Point& a, const Point& b, const Point& c) {
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

static inline int ccw(const Point& a, const Point& b, const Point& c) {
  long long v = cross(a, b, c);
  return (v > 0) - (v < 0);
}

// O(log N) convex polygon point inclusion (vertices CCW)
static bool insideConvexLog(const vector<Point>& poly, const Point& p) {
  int n = (int)poly.size();
  if (ccw(poly[0], poly[1], p) < 0) return false;
  if (ccw(poly[0], poly[n - 1], p) > 0) return false;
  int l = 1, r = n - 1;
  while (l + 1 < r) {
    int m = (l + r) >> 1;
    if (ccw(poly[0], poly[m], p) >= 0) l = m; else r = m;
  }
  return ccw(poly[l], poly[r], p) >= 0;
}

static const int MAXN = 5000;
static const int SUMSZ = 2 * MAXN + 10;

static Point ext[2 * MAXN + 5];   // polygon duplicated
static int nxt1[MAXN + 5], nxt2[MAXN + 5];
static int sum1[SUMSZ], sum2[SUMSZ];

// For inside point p: for each i, find largest j in (i, i+n] with ccw(poly[i], poly[j], p) > 0
static void get_next(int n, const Point& p, int* arr) {
  int j = 1; // ensure j >= i+1
  for (int i = 0; i < n; ++i) {
    if (j < i + 1) j = i + 1;
    while (j + 1 < i + n && ccw(ext[i], ext[j + 1], p) > 0) ++j;
    arr[i] = j; // index in [i+1, i+n-1]
  }
}

// Both inside: number of diagonals crossed by segment p1-p2
static long long move_inside_count(int n, const int* a, const int* b) {
  long long tot = 0;
  for (int i = 0; i < n; ++i) tot += llabs((long long)a[i] - (long long)b[i]);
  return tot >> 1;
}

// Inside point p: minimal diagonals to exit polygon through some edge (then +1 boundary edge)
static int move_outside_cost(int n, const int* arr) {
  int len = 2 * n;
  memset(sum1, 0, sizeof(int) * (len + 2));
  memset(sum2, 0, sizeof(int) * (len + 2));

  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] += 1;
    sum2[i - 1 + n] -= 1;

    sum1[i + 1] += j;
    sum1[j] -= j;

    sum2[i + 1] -= 1;
    sum2[j] += 1;
  }

  for (int i = 1; i < len; ++i) {
    sum1[i] += sum1[i - 1];
    sum2[i] += sum2[i - 1];
  }

  int best = INT_MAX;
  for (int i = 0; i < n; ++i) {
    int now = sum1[i] + i * sum2[i];
    now += sum1[i + n] + (i + n) * sum2[i + n];
    if (now < best) best = now;
  }
  return (best >> 1) + 1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; 
  if (!(cin >> n)) return 0;
  vector<Point> poly(n);
  for (int i = 0; i < n; ++i) cin >> poly[i].x >> poly[i].y;

  for (int i = 0; i < n; ++i) {
    ext[i] = poly[i];
    ext[i + n] = poly[i];
  }

  int q; 
  cin >> q;
  while (q--) {
    Point p1, p2;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;

    bool in1 = insideConvexLog(poly, p1);
    bool in2 = insideConvexLog(poly, p2);

    if (!in1 && !in2) {
      cout << 0 << '\n';
      continue;
    }

    if (!in1 && in2) {
      swap(p1, p2);
      swap(in1, in2);
    }

    // p1 is inside
    get_next(n, p1, nxt1);
    int t1 = move_outside_cost(n, nxt1);

    if (!in2) {
      cout << t1 << '\n';
      continue;
    }

    // both inside
    get_next(n, p2, nxt2);
    int t2 = move_outside_cost(n, nxt2);
    long long crossInside = move_inside_count(n, nxt1, nxt2);
    cout << min<long long>(crossInside, (long long)t1 + t2) << '\n';
  }
  return 0;
}