CF75E-Ship's-Shortest-Path

计算几何方法存点、算边来建图，然后跑一边最短路就行了。这题水到Floyd都能过。。。

我们先连接起始点(s)和终点(t)。如果st不与多边形相交或与多边形的一条边重合，则直接输出st的长度。否则，建一个由s、t、st与多边形的两个交点、多边形的端点组成的图。若这张图中有两点为端点的线段不与多边形相交，则这两个点之间建一条边权为从一点走到另一点费用的边。最后求s、t两点的最短路即可。

代码如下：

#include <bits/stdc++.h>
#define cross(a, b) ((conj(a) * (b)).imag())
#define X real()
#define Y imag()
using namespace std;

typedef complex<double> point;

const double eps = 1e-9;

int cmp(double a, double b) {
  if (fabs(a - b) < eps)
    return 0;
  return a > b ? 1 : -1;
}

struct set_cmp {
  bool operator()(const point &A, const point &B) const {
    if (cmp(A.X, B.X))
      return A.X < B.X;
    if (cmp(A.Y, B.Y))
      return A.Y < B.Y;
    return 0;
  }
};

double len(point A, point B) { return hypot(A.X - B.X, A.Y - B.Y); }

bool segement(point A, point B, point R) {
  return cmp(len(A, B), len(A, R) + len(B, R)) == 0;
}

bool inter(point A, point B, point P, point Q, point &R) {
  double d1 = cross(P - A, B - A);
  double d2 = cross(Q - A, B - A);
  if (cmp(d1, d2) == 0)
    return false;
  R = (d1 * Q - d2 * P) / (d1 - d2);
  if (!segement(A, B, R) || !segement(P, Q, R))
    return false;
  return true;
}

int n;
point st, en;
vector<point> pol;

double g[34][34];

int main() {
  int x, y;
  cin >> x >> y;
  st = point(x, y);
  cin >> x >> y;
  en = point(x, y);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x >> y;
    pol.push_back(point(x, y));
  }
  double ans = len(st, en);
  set<point, set_cmp> intrs;
  for (int i = 0; i < n; i++) {
    point R;
    if (inter(st, en, pol[i], pol[(i + 1) % n], R))
      intrs.insert(R);
  }
  if (intrs.size() == 2) {
    point p1 = *intrs.begin();
    point p2 = *(++intrs.begin());
    for (int i = 0; i < n + 4; i++) {
      for (int j = 0; j < n + 4; j++)
        g[i][j] = 1 << 30;
      g[i][i] = 0;
    }
    if (cmp(len(p2, st), len(p1, st)) < 0)
      swap(p1, p2);
    g[0][2] = g[2][0] = len(st, p1);
    g[1][3] = g[3][1] = len(en, p2);
    g[2][3] = g[3][2] = len(p1, p2) * 2;
    for (int i = 0; i < n; i++) {
      int i1 = i + 4;
      int i2 = (i + 1) % n + 4;
      g[i1][i2] = g[i2][i1] = len(pol[i1 - 4], pol[i2 - 4]);
      if (segement(pol[i1 - 4], pol[i2 - 4], p1)) {
        if (segement(pol[i1 - 4], pol[i2 - 4], p2))
          return printf("%.9lf\n", ans), 0;
        g[2][i1] = g[i1][2] = len(pol[i1 - 4], p1);
        g[2][i2] = g[i2][2] = len(pol[i2 - 4], p1);
      }
      if (segement(pol[i1 - 4], pol[i2 - 4], p2)) {
        g[3][i1] = g[i1][3] = len(pol[i1 - 4], p2);
        g[3][i2] = g[i2][3] = len(pol[i2 - 4], p2);
      }
    }
    n += 4;
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    ans = g[0][1];
  }
  printf("%.9lf\n", ans);
}