过河

GitHub跳转原题关系图返回列表

把每块圆盘看成「木桩×圆盘种类」的带权点,相交或相切即连边,触底盘与触顶盘分别当源点和汇点,跑一遍点权 Dijkstra 求最小花费。

OJ: roj

题目 ID: 1719

难度:提高+/省选-

标签:图论最短路计算几何python

创建: 2026-10-07 18:50

更新: 2026-10-07 18:50

形式化题目

河是平面直角坐标系里 0⩽y⩽W0 \leqslant y \leqslant W 的无限长带状区域。河面上有 NN 个木桩,第 kk 个木桩位于 (Xk,Yk)(X_k, Y_k);另有 MM 种圆形木头,第 kk 种半径 RkR_k、单价 CkC_k,每种都可以买任意多块。

每买一块圆盘,必须把它的圆心放在某个木桩上(同一木桩上可以放任意多块,圆盘允许伸出河面, 即圆盘上 y<0y < 0 或 y>Wy > W 的部分照样算在可行走范围里)。

EE 只能在直线 y=0y = 0、直线 y=Wy = W 以及买下的圆盘上移动,“相切的两者之间可以移动”。 也就是说:圆盘 uu 与圆盘 vv 之间可通行当且仅当两圆心距离 d(u,v)⩽Ru+Rvd(u, v) \leqslant R_u + R_v; 圆盘 uu 与底边 y=0y = 0 相通当且仅当 Yu⩽RuY_u \leqslant R_u;与顶边 y=Wy = W 相通当且仅当 W−Yu⩽RuW - Y_u \leqslant R_u。

求一组购买的圆盘(每个元素是"某个木桩 + 某种圆盘"),使得底边与顶边连通,且总价最小; 不存在这样的方案时输出 impossible。

规模:1⩽T⩽101 \leqslant T \leqslant 10,1⩽N,M⩽2501 \leqslant N, M \leqslant 250,2⩽W⩽1092 \leqslant W \leqslant 10^9, 0⩽Xk⩽1090 \leqslant X_k \leqslant 10^9,1⩽Yk⩽W1 \leqslant Y_k \leqslant W,1⩽Rk⩽1091 \leqslant R_k \leqslant 10^9,1⩽Ck⩽1061 \leqslant C_k \leqslant 10^6。

正解

思路

第一步:把"买一堆盘"化简成"一条链"。

设买下的圆盘集合是 SS(SS 中每个元素是"某个木桩 + 某种圆盘")。在 SS 上建一张无向图: 两圆盘相邻当且仅当圆心距不超过半径之和,再把底边、顶边各看作一个点, 底边连着所有满足 Yu⩽RuY_u \leqslant R_u 的圆盘,顶边连着所有满足 W−Yu⩽RuW - Y_u \leqslant R_u 的圆盘。 "能走过去"就是这张图里底边与顶边连通。

底边与顶边连通,当且仅当存在一条底边到顶边的路径 PP。路径是 SS 的子集, 所以买 PP 里那几块盘就够了,而且价格只会更少。于是最优解一定是一条链,不会出现分叉。 (链上同一种盘可以在不同木桩上出现多次,价格按块数累加;而链上每个 "木桩 + 圆盘种类"的组合只出现一次——最短路不会绕回同一个点,绕回只会白花钱。)

第二步:点权最短路。

把节点定成 (木桩,圆盘种类)(\text{木桩}, \text{圆盘种类}),节点权就是这块圆盘的价格。 那么一条从底边到顶边的链,价格之和正是路径上所有节点的点权之和。 再加一个权为 00 的源点 SS(底边)和一个权为 00 的汇点 TT(顶边):

  • S→(i,a)S \to (i, a),若 Yi⩽RaY_i \leqslant R_a(这块盘触底);
  • (i,a)→(k,b)(i, a) \to (k, b),若 d(i,k)⩽Ra+Rbd(i, k) \leqslant R_a + R_b(两块盘相交或相切);
  • (i,a)→T(i, a) \to T,若 W−Yi⩽RaW - Y_i \leqslant R_a(这块盘触顶)。

答案就是 SS 到 TT 的点权最短路。点权用"首次到达该点时付掉节点权"的常规办法处理, 即 dist[i][a]\mathrm{dist}[i][a] 表示以"停在木桩 ii 上的第 aa 种圆盘"收尾的最小花费(已含这块盘的钱), 初始值 dist[i][a]=Ca\mathrm{dist}[i][a] = C_a(当 Yi⩽RaY_i \leqslant R_a),转移为

dist[k][b]=min⁡{ dist[i][a]+Cb  ∣  ⌈d(i,k)⌉⩽Ra+Rb }, \mathrm{dist}[k][b] = \min\Bigl\{\, \mathrm{dist}[i][a] + C_b \;\Bigm|\; \lceil d(i,k) \rceil \leqslant R_a + R_b \,\Bigr\},

答案 =min⁡{ dist[i][a]∣W−Yi⩽Ra }= \min\{\, \mathrm{dist}[i][a] \mid W - Y_i \leqslant R_a \,\}。

这里必须把状态定成"木桩 + 种类"而不是"某一条边",是因为同一块盘可以同时接住前后两段: 走到木桩 ii 时用的是第 aa 种盘,从这里再跳到下一根木桩,用的还是这同一块盘, 它的价格只能算一次。若把状态定成边,中间节点的钱就会被重复计入。

第三步:距离全部用整数。 浮点开方在 10910^9 量级容易出偏差, 而 d⩽Ra+Rb  ⟺  ⌈d⌉⩽Ra+Rbd \leqslant R_a + R_b \iff \lceil d \rceil \leqslant R_a + R_b(右端是整数), 所以只要预处理出圆心距的向上取整 ⌈d(i,k)⌉=⌈Δx2+Δy2⌉\lceil d(i,k) \rceil = \lceil \sqrt{\Delta x^2 + \Delta y^2} \rceil (用 isqrt / sqrtl 加一步修正,全程整数),判定就完全精确了。

第四步:Pareto 压缩圆盘种类。 如果存在另一种盘 (R′,C′)(R', C') 满足 R′⩾RR' \geqslant R 且 C′⩽CC' \leqslant C, 那么 (R,C)(R, C) 永远不划算:换 (R′,C′)(R', C') 站得更远、还更便宜。把这种被支配的种类删掉后, 保留下来的前沿满足 RR 升序、CC 严格升序,长度 P⩽MP \leqslant M。 这样一来,"半径至少为 need\mathrm{need} 的种类"恰好是一段下标后缀 [idx,P)[\mathrm{idx}, P), 可以二分定位;后面还会用到"后缀"这个性质。

第五步:让每个状态只被松弛一次。 直接枚举转移是 NMN M 个状态 ×\times NMN M 条出边 =O(N2M2)≈4×109= O(N^2M^2) \approx 4 \times 10^9,不行。

关键观察是:松弛的结果 base+Cb\mathrm{base} + C_b 对 base\mathrm{base} 单调不减。 堆优化 Dijkstra 的出堆顺序保证 base\mathrm{base} 单调不减,所以一个状态 第一次被覆盖时拿到的值就是它的最终最短路,之后再被覆盖只会更差。

于是维护 frontier[k]\mathrm{frontier}[k]:木桩 kk 上"还没定最短路"的最小下标, [frontier[k],P)[\mathrm{frontier}[k], P) 这一段已经定好了(初始 frontier[k]=P\mathrm{frontier}[k] = P,表示一块都还没定)。 每次弹出 (i,a)(i, a)、花费 vv 时,对每根木桩 kk 算出 need=⌈d(i,k)⌉−Ra\mathrm{need} = \lceil d(i,k) \rceil - R_a,二分得到后缀起点 idx\mathrm{idx}, 就把 [idx,frontier[k])[\mathrm{idx}, \mathrm{frontier}[k]) 这一段整体松弛成 v+Cbv + C_b,然后把 frontier[k]\mathrm{frontier}[k] 收缩到 idx\mathrm{idx}。 由于每根木桩被覆盖的永远是"从某个位置到末尾"的后缀,而收缩是单调的, 每个状态入堆至多一次,堆大小不超过 NPN P,每次弹堆的代价是 O(Nlog⁡P)O(N \log P)。

第六步:无解与提前退出。 出堆时如果 Ra⩾W−YiR_a \geqslant W - Y_i,说明这块盘触顶了; 因为出堆花费单调不减,这个 vv 就是答案,可以直接 break。堆空了还没触顶,输出 impossible。

以样例第 1 组为例(W=13W = 13,答案 206206),最优链是

顺序 木桩坐标 圆盘 (R,C)(R, C) 累计花费
1(触底) (4,2)(4, 2) (2,1)(2, 1) 1
2 (4,6)(4, 6) (2,1)(2, 1) 2
3 (8,7)(8, 7) (3,100)(3, 100) 102
4 (11,4)(11, 4) (2,1)(2, 1) 103
5 (15,4)(15, 4) (2,1)(2, 1) 104
6 (19,4)(19, 4) (2,1)(2, 1) 105
7 (19,5)(19, 5) (2,1)(2, 1) 106
8(触顶) (19,10)(19, 10) (3,100)(3, 100) 206

6×1+2×100=2066 \times 1 + 2 \times 100 = 206,正好对应样例输出;第 2 组答案是 5=3+25 = 3 + 2, 第 3 组因为唯一的圆盘半径只有 11、木桩又在 y=5×108y = 5 \times 10^8 处,两边都够不到,输出 impossible。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:50
# update_at: 2026-10-07 18:50

import sys
from bisect import bisect_left
from heapq import heappop, heappush
from math import isqrt

INF = 10 ** 18   # 最短路无穷大:远大于任何可行花费(<= 250 * 10^6)

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Pile = tuple[int, int]             # 木桩坐标 (X, Y)
type Disk = tuple[int, int]             # 圆盘种类 (R, C),半径与价格


def ceil_sqrt(s: int) -> int:
    """返回最小的 r 使 r*r >= s,即圆心距的整数向上取整。"""
    r = isqrt(s)
    return r if r * r >= s else r + 1


def pareto_front(disks: list[Disk]) -> tuple[list[int], list[int]]:
    """把圆盘种类压成 Pareto 前沿,返回(半径表, 价格表),两者都升序。

    "半径更大且价格不更高"的种类可以完全替代另一种(够得更远还更便宜),
    故只保留不被支配的:按半径从大到小扫,价格必须比所有更大半径的种类都低才留下。
    """
    cheapest = {}                       # 半径 -> 该半径下的最低价格
    for radius, cost in disks:
        if cost < cheapest.get(radius, INF):
            cheapest[radius] = cost
    radii: list[int] = []
    costs: list[int] = []
    floor = INF                         # 已保留种类(半径都比当前这个大)中的最低价格
    for radius in sorted(cheapest, reverse=True):
        if cheapest[radius] < floor:    # 半径更小却更便宜,才没被支配
            radii.append(radius)
            costs.append(cheapest[radius])
            floor = cheapest[radius]
    radii.reverse()                     # 翻成半径升序,价格随之升序
    costs.reverse()
    return radii, costs


def cheapest_bridge(piles: list[Pile], disks: list[Disk], river_w: int) -> int | None:
    """返回从 y=0 走到 y=W 的最小花费,无解返回 None。

    节点 = (木桩, 圆盘种类),节点权 = 圆盘价格:所有触底盘是源点、任意触顶盘是终点,
    于是答案就是从地面到河对岸的点权最短路。
    """
    bl = bisect_left                    # 内层循环要跑 10^7 次,绑定成局部名省一次全局查找
    radii, costs = pareto_front(disks)
    n, p = len(piles), len(radii)
    # 圆心距向上取整:d <= r1 + r2 等价于 ceil(d) <= r1 + r2,全程整数比较
    gap = [[ceil_sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) for x2, y2 in piles] for x1, y1 in piles]

    frontier = [p] * n                  # 木桩 k 上 [frontier[k], p) 已定最短路,前面还待松弛
    dist = [[INF] * p for _ in range(n)]
    heap: list[tuple[int, int, int]] = []
    live = list(range(n))               # frontier > 0 的木桩:只有它们还有待松弛的圆盘

    def relax(k: int, idx: int, base: int) -> None:
        """用花费 base 松弛木桩 k 上尚未定最短路的圆盘 [idx, frontier[k])。

        出堆的 base 单调不减、松弛结果 base + 价格对 base 单调,
        所以每个 (木桩, 圆盘) 状态第一次被覆盖时拿到的就是它的最终最短路。
        """
        for t in range(idx, frontier[k]):
            dist[k][t] = base + costs[t]
            heappush(heap, (dist[k][t], k, t))
        frontier[k] = idx
        if idx == 0:
            live.remove(k)              # 整根木桩都定完了,退出活跃表

    for k, (_, y) in enumerate(piles):
        relax(k, bl(radii, y), 0)       # 源点:半径 >= Y_k 的圆盘触底,代价 0 起

    while heap:
        cost, i, a = heappop(heap)
        if cost != dist[i][a]:
            continue
        if radii[a] >= river_w - piles[i][1]:
            return cost                  # 该盘触顶,出堆顺序保证这就是最小花费
        row, shift = gap[i], -radii[a]   # 跳到木桩 k 需要半径 >= 圆心距 - R_a
        for k in live[:]:                # 快照遍历:relax 会把定完的木桩移出 live
            idx = bl(radii, row[k] + shift)
            if idx < frontier[k]:
                relax(k, idx, cost)
    return None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    test_count = next(data)

    for _ in range(test_count):
        n, m = next(data), next(data)
        river_w = next(data)
        piles: list[Pile] = [(next(data), next(data)) for _ in range(n)]
        disks: list[Disk] = [(next(data), next(data)) for _ in range(m)]
        best = cheapest_bridge(piles, disks, river_w)
        out.append('impossible' if best is None else str(best))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 18:50
 * update_at: 2026-10-07 18:50
 */
// main.cpp:过河(一本通 · 高手训练 1719)。
// 可行走集合 = 直线 y=0、直线 y=W 与买下的若干圆盘(含边界与内部)。
// 圆心必须放在某个木桩上,圆盘可以伸出河面(y<0 或 y>W)。
// 两圆盘能互相走到 ⇔ 圆心距 d <= r1 + r2(相切/相交即可);
// 圆盘触底 ⇔ Y <= R,触顶 ⇔ W - Y <= R。
// 于是问题化成"点权(圆盘价格)最短路":节点 = (木桩, 圆盘种类),节点权 = 圆盘价格,
// 所有触底的圆盘是源点(以 0 为初始代价),任意触顶的圆盘是终点。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 255;      // 木桩数量上限,题面 N <= 250
const int MAXM = 255;      // 圆盘种类上限,题面 M <= 250
const ll INF = 4000000000000000000LL;   // 最短路无穷大,远大于任何可行花费(<= 250 * 10^6)

// 一根木桩:圆心只能放在这里,坐标 (x, y)
struct Pile {
    ll x;
    ll y;
};

// 一种圆盘:半径 r、单价 c
struct Disk {
    ll r;
    ll c;
};

// 堆中元素:停在木桩 pile 上、用的是第 disk 种圆盘时的总花费 cost
struct State {
    ll cost;
    ll pile;
    ll disk;
    // priority_queue 默认大根堆,这里反向比较,得到按 cost 的小根堆
    bool operator<(const State &other) const { return cost > other.cost; }
};

int pileCnt;                // 木桩数 N
int diskTypeCnt;            // 读入的圆盘种类数 M
ll riverW;                  // 河的宽度 W
ll typeCnt;                 // 压缩后保留下来的圆盘种类数(Pareto 前沿长度),也当"种类下标"的上界用
Pile pile[MAXN];            // 木桩
Disk disk[MAXM];            // 保留的圆盘,半径升序、价格随之严格升序
ll pileDist[MAXN][MAXN];    // pileDist[i][k] = 木桩 i 与木桩 k 的圆心距向上取整(整数比较,免浮点误差)
ll dist[MAXN][MAXM];        // dist[i][a]:从地面一路走到"停在木桩 i 上的第 a 种圆盘"的最小花费
ll frontier[MAXN];          // 木桩 k 上下标 >= frontier[k] 的圆盘已定最短路,[0, frontier[k]) 还待松弛

priority_queue<State> pq;   // 堆优化 Dijkstra 的优先队列

// 返回最小的整数 r >= 0 使 r*r >= s,即 ceil(sqrt(s));圆心距全程用整数表示
ll ceil_sqrt(ll s) {
    if (s <= 0) return 0;
    ll r = sqrtl(s);        // 先取浮点近似,下面两个 while 把它修正成精确的整数开方
    while (r > 0 && (r - 1) * (r - 1) >= s) r--;
    while (r * r < s) r++;
    return r;
}

// 读入 M 种圆盘并压缩成 Pareto 前沿:半径升序、价格严格升序。
// "半径更大且价格不更高"的种类可以完全替代另一种(够得更远、还更便宜),故只保留不被支配的。
void read_disks() {
    map<ll, ll> cheapest;   // 半径 -> 该半径下的最低价格,只为同半径去重
    for (int i = 0; i < diskTypeCnt; i++) {
        ll radius, cost;
        scanf("%lld %lld", &radius, &cost);
        map<ll, ll>::iterator it = cheapest.find(radius);
        if (it == cheapest.end() || cost < it->second) cheapest[radius] = cost;
    }
    typeCnt = 0;
    ll floor = INF;         // 已保留种类(半径都比当前这个大)中的最低价格
    for (map<ll, ll>::reverse_iterator it = cheapest.rbegin(); it != cheapest.rend(); ++it) {
        if (it->second < floor) {   // 半径更小却更便宜,才没被"更大更便宜的盘"支配
            disk[typeCnt].r = it->first;
            disk[typeCnt].c = it->second;
            typeCnt++;
            floor = it->second;
        }
    }
    reverse(disk, disk + typeCnt);  // 翻成半径升序,价格随之升序
}

// 二分出第一个半径 >= need 的种类下标:半径表升序,故"半径够用"的种类恰好是一段后缀
ll lower_bound_radius(ll need) {
    ll lo = 0, hi = typeCnt;    // 答案落在 [lo, hi],hi 表示"没有种类够用"
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (disk[mid].r >= need) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

// 用花费 base 一次性松弛木桩 k 上尚未定最短路的圆盘 [idx, frontier[k])。
// 每次出堆的 base 单调不减,而松弛结果 base + c 对 base 单调,
// 所以每个 (木桩, 圆盘) 状态第一次被覆盖时拿到的就是它的最终最短路。
void relax_pile(ll k, ll idx, ll base) {
    for (ll t = idx; t < frontier[k]; t++) {
        dist[k][t] = base + disk[t].c;
        State cur;
        cur.cost = dist[k][t];
        cur.pile = k;
        cur.disk = t;
        pq.push(cur);
    }
    frontier[k] = idx;
}

int main() {
    int testCnt;
    if (scanf("%d", &testCnt) != 1) return 0;

    while (testCnt--) {
        scanf("%d %d %lld", &pileCnt, &diskTypeCnt, &riverW);
        for (int i = 0; i < pileCnt; i++) scanf("%lld %lld", &pile[i].x, &pile[i].y);
        read_disks();

        // 圆心距预处理:ceil(两点欧氏距离)。d <= r1 + r2 等价于 ceil(d) <= r1 + r2
        for (int i = 0; i < pileCnt; i++) {
            for (int k = 0; k < pileCnt; k++) {
                ll dx = pile[i].x - pile[k].x;
                ll dy = pile[i].y - pile[k].y;
                pileDist[i][k] = ceil_sqrt(dx * dx + dy * dy);
            }
        }

        while (!pq.empty()) pq.pop();
        for (int k = 0; k < pileCnt; k++) {
            frontier[k] = typeCnt;                  // 一开始所有圆盘都没定最短路
            for (ll t = 0; t < typeCnt; t++) dist[k][t] = INF;
        }

        // 源点:能触底的圆盘(Y_k <= R),代价就是这块圆盘的价格
        for (int k = 0; k < pileCnt; k++) relax_pile(k, lower_bound_radius(pile[k].y), 0);

        ll ans = -1;
        while (!pq.empty()) {
            State cur = pq.top();
            pq.pop();
            if (cur.cost != dist[cur.pile][cur.disk]) continue;
            if (disk[cur.disk].r >= riverW - pile[cur.pile].y) {   // 这块圆盘触顶了
                ans = cur.cost;
                break;                                             // 出堆顺序单调不减,首次触顶即最优
            }
            for (int k = 0; k < pileCnt; k++) {
                if (frontier[k] == 0) continue;                    // 木桩 k 上已无可松弛的圆盘
                // 从当前圆盘跳到木桩 k:需要半径 >= 圆心距 - R_cur,仍是一段后缀
                ll idx = lower_bound_radius(pileDist[cur.pile][k] - disk[cur.disk].r);
                if (idx < frontier[k]) relax_pile(k, idx, cur.cost);
            }
        }

        if (ans < 0) printf("impossible\n");
        else printf("%lld\n", ans);
    }
    return 0;
}

复杂度

  • 时间:预处理圆心距 O(N2)O(N^2);Dijkstra 中每个状态至多入堆一次,共 O(NP)O(NP) 次出堆, 每次出堆对 NN 根木桩各做一次二分,单组数据 O(N2Plog⁡P)⊆O(N2Mlog⁡M)O(N^2 P \log P) \subseteq O(N^2 M \log M), 共 O(T⋅N2Mlog⁡M)O(T \cdot N^2 M \log M)。取 N=M=250N = M = 250 上界约 1.6×1071.6 \times 10^7 次内层操作, C++ 实测最坏数据点(problem9,T=10T = 10 组全连通但触不到顶、所有状态都要弹出)0.49 s, 限时 2000 ms。Python 版因为内层循环在解释器里跑,同一数据点约 2.0 s, 超出本题 2000 ms 的限时,属于"算法同阶但常数不够"的 TLE 风险(见 ## 总结)。
  • 空间:圆心距矩阵 O(N2)O(N^2),dist\mathrm{dist} 表 O(NP)⊆O(NM)O(NP) \subseteq O(NM), 堆 O(NP)O(NP),单组数据约 O(N2+NM)O(N^2 + NM),取上界约 6.3 万个 long long 加一个 250×250250 \times 250 的距离矩阵, C++ 实测峰值 8.3 MB,限时内存 256 MB。
  • Python 与 C++ 的关系:main.py 与 main.cpp 是同一算法、同一复杂度的两个实现, 只是 Python 版额外用 live 活跃表把"已经全部定完最短路的木桩"从内层循环里摘掉, 最坏数据点因此从 2.9 s 降到 2.0 s;C++ 版靠 frontier[k] == 0 的判断达到同样效果。
  • 正确性验证:main.cpp 与 main.py 除逐点跑通素材的 10 个数据点外, 还与一份不剪枝的稠密版 Dijkstra(显式枚举所有 (木桩,种类)(\text{木桩},\text{种类}) 点对、 O(N2M2)O(N^2M^2))做了 1800 组随机小数据对拍,结果完全一致。

总结

  • 先做模型化简,再谈算法:题目问的是"买一堆盘让两岸连通", 但连通只需一条路径,路径是任意方案的子集,于是最优化问题直接退化成最短路。 这一步把"选集合"的不确定性彻底消掉了。
  • 节点权而不是边权:把状态定成"木桩 + 圆盘种类"、价格记在点上, 才能让中间木桩上那同一块盘同时接住前后两段而不重复计费。
  • 单调性换来"每个状态只松弛一次":base+Cb\mathrm{base} + C_b 对 base\mathrm{base} 单调, 配合出堆顺序单调不减,就能用"后缀 + frontier 收缩"把 O(N2M2)O(N^2M^2) 的稠密转移压到 O(N2Mlog⁡M)O(N^2M\log M)。这是本题最核心的一步,也是"堆优化 Dijkstra 中节点只会被最终确定一次"的典型用法。
  • Pareto 剪枝顺手把二分做好了:删掉"更大更便宜"能支配的种类之后, 半径表升序、价格也升序,"半径至少 need\mathrm{need}"自然变成一段后缀,二分和区间松弛都能直接用。
  • 几何判定别碰浮点:d⩽Ra+Rb  ⟺  ⌈d⌉⩽Ra+Rbd \leqslant R_a + R_b \iff \lceil d \rceil \leqslant R_a + R_b, 把圆心距向上取整成整数即可,X,Y,RX, Y, R 上到 10910^9 也不会有精度风险。
  • 数据说明:本题素材目录里带数据生成脚本(data.py),说明测试数据是依据题面自造的, 题面本身也是从网络重建的(pic/1719.jpg 无对应图片文件),出题意图与官方原题可能有细微偏差。 素材中的 std.cpp 与本文模型一致,10 个数据点全部与题面样例吻合,本文实现亦与它逐点一致。