[ICPC] 백준 3861 - Slalom

https://www.acmicpc.net/problem/3861

아이디어

최단 경로는 변위가 작은, 다시 말해 가능한 한 회전을 하지 않을 때 성립한다. 조금 쉬운 예시로 다음 그림을 보면 좋다.

 

꺾지 않는 최장 직선 찾기

그러면 우리는 한 직선 이동에 게이트를 많이 지나는 방법을 찾아야 한다. 그러기 위해 우리는 다음 고려할 것이다.

 

어떤 게이트 끝점에서 직선으로 최대한 도달할 수 있는 게이트는 어디인가?

 

좀 더 생각하면 반드시 회전을 해야만 할 때 탐욕적으로 다음 게이트의 끝점에만 가면 됨을 알 수 있다.

 

이 사실을 통해 우리는 어떤 게이트의 끝점(시작점 포함)에서 출발할 때 다음 게이트의 끝점을 경유해야만 하는지, 그렇지 않아도 다음 게이트를 통과할 수 있는지 검사하면 충분하다는 생각을 할 수 있다.

 

그러면 최대로 도달 가능한 게이트는 무엇이고. 그것의 최단 경로는 어떻게 계산해야 하는가?

 

끝점이 두 개이므로 다양한 분기가 나오게 된다. 따라서 우리는 이 각 직선 경로를 dp로 저장해야만 한다.

 

스키 시작점을 기준으로 아래 방향으로 광선을 쓰다 보면 다음과 같은 그림을 볼 수 있다.

 

 

밑으로 수많은 광선을 쐈을 때 최대한 최단 경로 광선을 찾아내면 된다... 만 우리 PS에서는 그런 거 쉽지 않으므로 각 게이트의 끝점을 지나거나, 지나지 않고 끝에 도달할 수 있는지 이를 일일이 검사할 것이다.

 

동적 계획법 전개

우리는 다음과 같은 방식으로 dp를 계산할 것이다.

 

 

결승점부터 테이블을 채우는 방식으로 시작점 dp(0, 0)까지 거슬러 올라가도록 한다.

 

물론 그림에도 썼듯이 게이트로 꺾지 않고 직진으로 결승점에 도달 가능한 경우도 고려해야 한다.

게이트 통과 검사 - 꺾어야 하는 경우 판별

그러면 각 게이트에서 어디까지 갈 수 있는지 검사해보자. 동적 계획법을 뒤부터 채울 것이므로 검사도 당연 뒤의 게이트의 점을 기준으로 검사를 시작한다.

 

좀 더 쉽게 하기 위해 다음 두 게이트에 지나려면 회전해야 하는지 확인하도록 하자. 이는 CCW로 검사할 수 있으며 기준점 x와 현재 보존 중인 게이트 p, 검사할 게이트 q에 대해 다음 검사를 진행하면 된다.

 

그리고 검사를 진행하면서 끝점을 지나야만 하는 경우 이를 갱신하기 위해 게이트의 좌표를 보존하도록 한다.

 

1. ccw(x, q1, p2)가 양수일 경우

 

 

그림처럼 되어 반시계 판정이 되고 꺾어야 한다.

 

2. ccw(x, q2, p1)이 양수일 경우

 

 

그림처럼 반시계 판정이 되고 꺾어야 한다.

 

위 두 경우에 걸리면 직선 이동이 불가능하다. 한 번 꺾으면 두 번의 직선 이동이 있다는 소리고 직선 이동 거리에 대해선 글의 뒷부분에서 계산하므로 여기선 계산이 필요 없다. 따라서 검사를 종료한다.

게이트 통과 검사 - 회전이 필요 없지만 다음 게이트의 끝점을 지남

꺾지 않고 갈 수 있는 경우를 보자.

 

역시 두 경우로 나뉜다.

 

1. CCW(x, p1, q1) >= 0인 경우

일직선인 경우도 분명 포함될 수 있으므로 CCW 결과가 0 이상이면 다음 게이트의 끝점에 도달했을 때의 dp의 최적해를 계산할 필요가 있다.

 

2. CCW(x, q2, p2) >= 0

위와 같다.

 

위 검사 결과에 걸리면 다음 게이트의 끝점을 지나칠 수 있다는 뜻이다.

 

시작점 ~ 검사한 게이트 위치까지의 거리로 dp 테이블을 계산하고 현재 보존한 게이트 p의 끝점도 갱신하도록 한다.(이제 이전 게이트는 지나가버렸으므로 의미가 없다.)

마지막에 도달한 경우

이렇게 p를 갱신하다가 마침내 마지막 게이트에 도달이 가능함을 확인하면 해당 기준점 ~ 결승 게이트까지 직선 이동이 가능하다는 뜻이다.

 

그런데 이런 경우 기울기가 무한(바로 아래로 꽂는 경우)이거나 그렇지 않은 경우(비스듬하게 이동한 경우)를 고려해서 도착 위치를 계산해야 한다. 이는 직선 교차 구현을 이용해 교차점을 간단히 구할 수 있다.

 

바로 내리 꽂았으면 경로 값은 y의 거리만큼 되고 그렇지 않으면 유클리드 거리를 계산하면 되시겠다.

 

각 케이스에 따라 구한 값을 dp 테이블에 반영해서 마지막 dp(0, 0)까지 계산하면 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
const double eps = 1e-9, inf = 1e300;
 
template<typename T>
struct point2 {
  T x, y;
  point2() : x(0), y(0) {}
  point2(T _x, T _y) : x(_x), y(_y) {}
 
  bool operator < (const point2<T> &r) const {
    if (typeid(T) == typeid(long long)) {
      if (x != r.x) return x < r.x;
      return y < r.y;
    } else {
      if (fabs(x - r.x) >= 1e-9) return x < r.x;
      return y < r.y;
    }
  }
 
  bool operator == (const point2<T> &r) const {
    if (typeid(T) == typeid(long long)) {
      return x == r.x and y == r.y;
    } else {
      return (fabs(r.x - x) < 1e-9 and fabs(r.y - y) < 1e-9);
    }
  }
};
 
template<typename T>
int ccw(point2<T> &p1, point2<T> &p2, point2<T> &p3) {
  T res = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
  if (fabs(res) < 1e-9) return 0;
  if (res < 0) return -1;
  return 1;
}
 
template<typename T>
double dist(point2<T> &p1, point2<T> &p2)
{
  return hypot(p1.x - p2.x, p1.y - p2.y);
}
 
template<typename T>
T det2(T a, T b, T c, T d) { return a*d - b*c; }
 
template<typename T>
struct line2 { T a, b, c; };
 
template<typename T>
bool line_equation(point2<T> &p, point2<T> &q, line2<T> &res) {
  if (p == q) return false;
  auto a = p.y - q.y, b = q.x - p.x;
  auto c = -a * p.x - b * p.y;
  if (a < 0 or (a == 0 and b < 0)) a *= -1, b *= -1, c *= -1;
  double de = 1;
  de = sqrt(a * a + b * b);
  res = {a / (T)de, b / (T)de, c / (T)de};
  return true;
}
 
template<typename T>
bool line_intersect(line2<T> &m, line2<T> &n, point2<double> &res) {
  auto zn = det2(m.a, m.b, n.a, n.b);
  if (typeid(T) == typeid(long long)) {
    if (zn == 0) return false;
  } else {
    if (fabs(zn) < 1e-9) return false;
  }
  res.x = -det2(m.c, m.b, n.c, n.b) / zn;
  res.y = -det2(m.a, m.c, n.a, n.c) / zn;
  return true;
}
 
int n;
double dp[1001][2];
point2<double> ar[1001][2];
line2<double> pivot;
 
void solve()
{
  cout.precision(15);
  cout << fixed;
 
  cin >> n;
 
  while (n)
  {
    fill(&dp[0][0], &dp[0][0] + 2 * 1001, inf);
    dp[n][0] = dp[n][1] = 0.;
 
    cin >> ar[0][0].x >> ar[0][0].y;
    ar[0][1] = ar[0][0];
 
    for (int i = 1; i <= n; i++)
    {
      double y, x1, x2;
      cin >> y >> x1 >> x2;
      ar[i][0].x = x1, ar[i][0].y = y;
      ar[i][1].x = x2, ar[i][1].y = y;
    }
 
    line_equation(ar[n][0], ar[n][1], pivot);
 
    for (int i = n - 1; i >= 0; i--)
    {
      int iter = 2;
      if (!i) --iter;
 
      for (int side = 0; side < iter; side++)
      {
        point2<double> tmp = ar[i][side];
 
        auto nxt1 = ar[i + 1][0], nxt2 = ar[i + 1][1];
 
        int j = i + 1;
        while (j <= n)
        {
          if (ccw(tmp, ar[j][1], nxt1) > 0 or ccw(tmp, nxt2, ar[j][0]) > 0)
          {
            // cannot go liner check by ccw
            break;
          }
 
          if (ccw(tmp, nxt1, ar[j][0]) >= 0)
          {
            nxt1 = ar[j][0];
            dp[i][side] = min(dp[i][side], dp[j][0] + dist(tmp, nxt1));
          }
 
          if (ccw(tmp, ar[j][1], nxt2) >= 0)
          {
            nxt2 = ar[j][1];
            dp[i][side] = min(dp[i][side], dp[j][1] + dist(tmp, nxt2));
          }
 
          ++j;
        }
 
        // Success to reach last gate
        // just calculate dp table
        if (j == n + 1)
        {
          double y = ar[n][0].y;
          line2<double> myline;
          line_equation(tmp, nxt1, myline);
          line_intersect(myline, pivot, nxt1);
          line_equation(tmp, nxt2, myline);
          line_intersect(myline, pivot, nxt2);
 
          double val;
          if (tmp.x > nxt2.x) 
          {
            val = dist(tmp, nxt2);
          }
          else if (tmp.x < nxt1.x)
          {
            val = dist(tmp, nxt1);
          }
          else
          {
            val = tmp.y - nxt1.y;
          }
          dp[i][side] = min(dp[i][side], val);
        }
      }
    }
 
    // dp direction: last gate -> start point
    cout << dp[0][0] << '\n';
 
    cin >> n;
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

 

제출 기록