Znzryb's Blog
0%

Gym 105158 D - 距离之比

Posted on

原题：Gym 105158 D 距离之比 ｜ vjudge

AC：vjudge solution 69896828

题目大意

平面上 nn 个互不重合的点 P1,…,PnP_1, \dots, P_n ，求

max⁡1≤i<j≤ndis1(Pi,Pj)dis2(Pi,Pj)\max_{1 \le i < j \le n} \frac{\mathrm{dis1}(P_i, P_j)}{\mathrm{dis2}(P_i, P_j)}

其中 dis1\mathrm{dis1} 是曼哈顿距离 ∣xi−xj∣+∣yi−yj∣|x_i - x_j| + |y_i - y_j| ， dis2\mathrm{dis2} 是欧几里得距离 (xi−xj)2+(yi−yj)2\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} 。

数据范围

  • 1≤T≤1051 \le T \le 10^5 组数据

  • 2≤n≤2×1052 \le n \le 2 \times 10^5 ， ∑n≤2×105\sum n \le 2 \times 10^5

  • ∣xi∣,∣yi∣≤109|x_i|, |y_i| \le 10^9

  • 输出绝对/相对误差 ≤10−9\le 10^{-9} 即可

思路讲解

一句话

比值 dis1/dis2\mathrm{dis1} / \mathrm{dis2} 只取决于两点连线的方向角， ±45∘\pm 45^\circ 方向最大 2\sqrt{2} 、坐标轴方向最小 11 。所以题目等价于"找方向最接近 ±45∘\pm 45^\circ 的点对"。一个中值不等式引理把它直接砍到 O(nlog⁡n)O(n \log n) ：按 x+yx + y 排序扫相邻、再按 x−yx - y 排序扫相邻就完事。

第 1 步：比值只取决于方向

设 θ\theta 是 PiPj→\overrightarrow{P_i P_j} 与 xx 轴的夹角。把 dis2\mathrm{dis2} 当分母提出来：

dis1dis2=∣cos⁡θ∣+∣sin⁡θ∣=2sin⁡ ⁣(∣θ′∣+π4)\frac{\mathrm{dis1}}{\mathrm{dis2}} = |\cos\theta| + |\sin\theta| = \sqrt{2}\sin\!\left(|\theta'| + \tfrac{\pi}{4}\right)

折叠到一个象限后看，整个比值是关于 θ\theta 的纯三角函数——也就是跟两点距离绝对长度无关、只看方向。

关键不变量： θ\theta 越接近 ±45∘\pm 45^\circ 或 ±135∘\pm 135^\circ ，比值越大；极大值 2≈1.4142\sqrt{2} \approx 1.4142 ； θ=0\theta = 0 或 π/2\pi/2 时退化为 11 。

第 2 步：旋转到 (u, v) 化为 Chebyshev

做仿射变换

u=x+y,v=x−yu = x + y, \qquad v = x - y

也就是把 xyxy 平面旋转 −45∘-45^\circ 再放缩 2\sqrt{2} 。神奇的事情发生了—— L1L^1 距离变成了 Chebyshev 距离：

dis1=max⁡(∣Δu∣,∣Δv∣),dis2=Δu2+Δv22\mathrm{dis1} = \max(|\Delta u|, |\Delta v|), \qquad \mathrm{dis2} = \sqrt{\frac{\Delta u^2 + \Delta v^2}{2}}

原 ±45∘\pm 45^\circ 方向在 (u,v)(u, v) 平面变成 uu 轴 / vv 轴方向。代入比值：

dis1dis2=2⋅max⁡(∣Δu∣,∣Δv∣)Δu2+Δv2\frac{\mathrm{dis1}}{\mathrm{dis2}} = \sqrt{2} \cdot \frac{\max(|\Delta u|, |\Delta v|)}{\sqrt{\Delta u^2 + \Delta v^2}}

不妨设 ∣Δu∣≥∣Δv∣|\Delta u| \ge |\Delta v| ，记 t=∣Δv∣/∣Δu∣∈[0,1]t = |\Delta v| / |\Delta u| \in [0, 1] ，比值化为 2/1+t2\sqrt{2} / \sqrt{1 + t^2} ——单调地越接近某根坐标轴（ t→0t \to 0 ）越大。

问题转化：在 (u,v)(u, v) 平面找点对，使其连线方向最接近 uu 轴或 vv 轴。

第 3 步：核心引理 — 中值不等式

转化后的问题：找一对点使 ∣(ui−uj)/(vi−vj)∣\left| (u_i - u_j) / (v_i - v_j) \right| 最大（以 vv 为横轴看"斜率绝对值最大"）。

引理：把点按 vv 升序排得 v(1)≤v(2)≤⋯≤v(n)v_{(1)} \le v_{(2)} \le \dots \le v_{(n)} 。最优点对必然出现在相邻位，即存在最优解 (P(k),P(k+1))(P_{(k)}, P_{(k+1)}) 。

证明（中值不等式）：取三点 i,k,ji, k, j 满足 vi<vk<vjv_i < v_k < v_j 。记 sab=(ub−ua)/(vb−va)s_{ab} = (u_b - u_a) / (v_b - v_a) 。则

sij=(uk−ui)+(uj−uk)(vk−vi)+(vj−vk)s_{ij} = \frac{(u_k - u_i) + (u_j - u_k)}{(v_k - v_i) + (v_j - v_k)}

分母两项同号，所以 sijs_{ij} 是 sik,skjs_{ik}, s_{kj} 的加权"中值"：

min⁡(sik,skj)≤sij≤max⁡(sik,skj)\min(s_{ik}, s_{kj}) \le s_{ij} \le \max(s_{ik}, s_{kj})

故 ∣sij∣≤max⁡(∣sik∣,∣skj∣)|s_{ij}| \le \max(|s_{ik}|, |s_{kj}|) 。

跨过中间点 kk 的非相邻对，其斜率绝对值不会超过两个跨界子对之一。一路归纳下去，最优解总能退化到 vv 排序后的相邻对。 □\square

中值不等式那一招很优美——它说"跨过去更长 ⇒\Rightarrow 不更陡"，本质上是凸性：把分子分母都看成"长度向量"沿 vv 轴的累加，斜率永远夹在子段斜率之间。这是一个比凸包/旋转卡壳更对路的工具，专门针对"对所有点对极大化方向相关量"这一类几何题。

第 4 步：完整算法

引理只处理了"方向最接近 uu 轴"。对称的"方向最接近 vv 轴"同理——按 uu 排序扫相邻对就能覆盖。所以：

  1. 按 u=x+yu = x + y 升序排，遍历相邻对更新最大比值

  2. 按 v=x−yv = x - y 升序排，遍历相邻对更新最大比值

  3. 两次累计的最大值就是答案

两次 sort + 两次 O(n)O(n) 扫描，单组 O(nlog⁡n)O(n \log n) 。每对的比值直接用原 (x,y)(x, y) 坐标算（无需真把点替换成 (u,v)(u, v) ）。

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
void Solve() {
    ll N; cin >> N;
    vector<Point<ll>> A(N);
    for (auto& p : A) cin >> p;

    auto upd = [&](Point<ll> a, Point<ll> b) {
        return (DB) distancePPL1(a, b) / distancePP(a, b);
    };

    // 阶段 1：按 u = x+y 升序排
    sort(all(A), [](auto& aO, auto& bO) {
        Point<ll> a(aO.x + aO.y, aO.x - aO.y);
        Point<ll> b(bO.x + bO.y, bO.x - bO.y);
        return a < b;
    });
    DB ans = 0;
    for (int i = 0; i + 1 < SZ(A); ++i)
        ans = max(ans, upd(A[i], A[i+1]));

    // 阶段 2：按 v = x-y 升序排（swap 后复用同一个 Point 字典序）
    sort(all(A), [](auto& aO, auto& bO) {
        Point<ll> a(aO.x + aO.y, aO.x - aO.y);
        Point<ll> b(bO.x + bO.y, bO.x - bO.y);
        swap(a.x, a.y); swap(b.x, b.y);
        return a < b;
    });
    for (int i = 0; i + 1 < SZ(A); ++i)
        ans = max(ans, upd(A[i], A[i+1]));

    cout << fsp(12) << ans << "\n";
}

几个实现细节：

  • distancePPL1 返回的是 __int128_t （我新加进几何模板的"曼哈顿距离"），所以 (DB) 强转一次再除浮点，不转的话整数除法直接出 1 全错

  • ∣x∣,∣y∣≤109|x|, |y| \le 10^9 ， dx2+dy2≤8×1018dx^2 + dy^2 \le 8 \times 10^{18} 卡在 long long 上界 9.2×10189.2 \times 10^{18} 内，不会爆 ll。要稳一点 __int128_t 兜底也行

  • 全程用 long double 配 sqrtl 保精度， cout << fixed << setprecision(12) 输出

  • 多组 T≤105T \le 10^5 ， ios::sync_with_stdio(false) 必须关掉缓冲

📎 动画与源码

完整的可交互 HTML 讲解我做了一份。覆盖 4 个 demo：

  1. 方向决定比值 ：拖一个点看比值随方向变化，验证"只看方向不看长度"

  2. xyxy ↔ uvuv 双视图：直观看到 ±45∘\pm 45^\circ 方向变 u,vu, v 轴的几何过程

  3. 中值不等式三点 demo ：拖中间点 kk 的 uu 坐标，看 sijs_{ij} 永远夹在 sik,skjs_{ik}, s_{kj} 之间

  4. 主算法 6 点演示 ：Step / Auto-play 走完两阶段排序 + 邻点扫，最优对正好在 P1-P2（u 都等于 7，Δu = 0，方向沿 v 轴 → 比值取到 2\sqrt{2} 上限）

HTML 本体 + 3 张关键帧截图都嵌在「附件」节里。

AC 代码

AC 提交 — vjudge solution 69896828

完整源码包含本次新沉淀进几何模板的：

  • Point::normL1() / Point::normLinf() 两个成员（曼哈顿 / 切比雪夫范数）

  • distancePP / distancePPL1 / distancePPLinf 三个自由函数（开方欧氏 / 曼哈顿 / 切比雪夫距离）

完整源码见末尾「📎 完整源码」附件 + 下方折叠块（折叠块走 raw API 单独追加，因为 30 KB 超 markdown 单段限制）。

心路历程

这道题没什么"卡 WA"的心路——主要是思路推导一条线下来：

  1. 看到 dis1/dis2\mathrm{dis1} / \mathrm{dis2} 直觉就反应"这跟方向有关"，写成 ∣cos⁡θ∣+∣sin⁡θ∣|\cos\theta| + |\sin\theta| 后就锁死"找最接近 ±45∘\pm 45^\circ 方向的点对"

  2. 但是 O(n2)O(n^2) 枚举显然不行（ ∑n=2⋅105\sum n = 2 \cdot 10^5 ），第一反应想凸包——结论：凸包做不了。反例：最优对可以在凸包内部。比如三角形 A=(0,0),B=(10,10),C=(10,−10)A = (0, 0), B = (10, 10), C = (10, -10) 加两个内部点 D=(5,0),E=(5,1)D = (5, 0), E = (5, 1) ， D,ED, E 的 Δu=0\Delta u = 0 比值直接 2\sqrt{2} 顶天，但 D,ED, E 都不在凸包上

  3. 直接看了官方题解才知道是中值不等式那一招。证明优美但"赛场上能不能想到"是另一回事——下次见到「对所有点对极大化方向相关量」类几何题先把这条工具拿出来用

  4. 实现时本来要在 Solve 里手写 L1 / L2 距离，顺手沉淀进几何模板（这次加了 distancePP / distancePPL1 / distancePPLinf 三个自由函数 + Point::normL1 / normLinf 两个成员），后续题目直接复用

Take-away：「最大化 / 最小化 f(θij)f(\theta_{ij}) 」（ θij\theta_{ij} 是点对方向角）这一类问题，先想"排序 + 邻点扫"配中值不等式，比凸包 / 旋转卡壳更对路。

附件

下面是这道题的可交互 HTML 讲解 + 3 张关键帧截图 + 完整源码下载。

distance_ratio.html.txt

Step 0：初始状态。6 个点已读入，未排序未扫描。

Step 6：u-排序阶段扫到最后一对 P5-P3 时，累计最优已锁定在 P1-P2（u 都 = 7，Δu = 0，方向沿 v 轴）—— 比值 1.414214 触顶 √2。

Step 12：算法完成。两阶段共扫了 10 对相邻对，最优对始终是 P1-P2。