P3493 WSP - Island

简要题意: 顺时针给出一个 $n$ 个顶点的凸多边形，任意两个顶点间都有一条线段。你需要沿着线段从 $1$ 走到 $n$，可以在线段的交点处移动到另一条线段上。现在有 $m$ 条线段不能走，但可以经过与其交叉点。问从 $1$ 走到 $n$ 的最短距离。

数据规模: $3 \le n \le 10^5,\ 1 \le m \le 10^6, \ |x|,|y| \le 10^6$。

题解: 观察下图。从 $A$ 到 $F$ 的最短路径一定是最靠近直线 $AF$ 的一条折线，即 $A \to P \to Q \to F$。因为在 $\triangle PQR$ 中，有 $PQ < PR + QR$。同理可证，在该题目中，从 $1$ 到 $n$ 的最短路径一定是最靠近 $1$ 和 $n$ 的连线的一条折线，即未被删除的线段所构成的下凸包。

但是未被删除的线段是 $O(n^2 - m)$ 量级的，不能枚举全部线段构造凸包。但注意到对于以 $s$ 为起点，以 $t_1$ 和 $t_2$ 为结束点的两条线段，若 $t_1 < t_2$，显然 $s-t_2$ 一定优于 $s-t_1$。因此，可以对于每个起点 $s$，简单求出最大的未被删除的 $t$，保留线段 $s-t$ 即可。

现在剩下 $O(n)$ 条线段，只需随意求出其构成的凸包即可。复杂度 $O(n)$ 或 $O(n \log n)$。

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
using ll = long long;
const int N = 1e5 + 10;
const double eps = 1e-6;
int n, m, top;
set<int> ban[N];
inline int sgn(const double &p) { return abs(p) <= eps ? 0 : (p < 0 ? -1 : 1); }
struct point {
  double x, y;
  point operator+(const point &p) const { return {x + p.x, y + p.y}; }
  point operator-(const point &p) const { return {x - p.x, y - p.y}; }
  point operator*(const double &k) const { return {x * k, y * k}; }
  point operator/(const double &k) const { return {x / k, y / k}; }
  double operator*(const point &p) const { return x * p.y - y * p.x; }
  double operator()() const { return hypot(x, y); }
} pt[N];
struct line {
  point p, v;
  point operator*(const line &s) const {
    double d = ((s.p - p) * s.v) / (v * s.v);
    return p + v * d;
  }
} sta[N];
signed main() {
  read(n), read(m);
  for (int i = 1; i <= n; ++i)
    read(pt[i].x), read(pt[i].y);
  for (int i = 1, u, v; i <= m; ++i)
    read(u), read(v), ban[u].insert(v);
  for (int i = 1, mx = 0; i <= n; ++i) {
    int to = n;
    while (to && ban[i].count(to))
      --to;
    if (to <= i || to <= mx)
      continue;
    line cur = {pt[i], pt[to] - pt[i]};
    if (top && sta[top].v * cur.v >= 0)
      continue;
    while (top > 1 && sta[top - 1].v * (sta[top] * cur - sta[top - 1].p) >= 0)
      --top;
    sta[++top] = cur, mx = to;
  }
  double ans = 0;
  point pre = pt[1];
  for (int i = 1; i <= top; ++i) {
    point nxt = (i == top) ? pt[n] : sta[i] * sta[i + 1];
    ans += (nxt - pre)(), pre = nxt;
  }
  printf("%.8lf\n", ans);
  return 0;
}

最后修改于 2025-07-05

Git 版本: de2abab