Gym 105158 D - 距离之比

Posted on 2026-05-15

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

AC：vjudge solution 69896828

题目大意

平面上 $n$ 个互不重合的点 $P_1, \dots, P_n$ ，求

\max_{1 \le i < j \le n} \frac{\mathrm{dis1}(P_i, P_j)}{\mathrm{dis2}(P_i, P_j)}

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

数据范围

$1 \le T \le 10^5$ 组数据
$2 \le n \le 2 \times 10^5$ ， $\sum n \le 2 \times 10^5$
$|x_i|, |y_i| \le 10^9$
输出绝对/相对误差 $\le 10^{-9}$ 即可

思路讲解

一句话

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

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

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

\frac{\mathrm{dis1}}{\mathrm{dis2}} = |\cos\theta| + |\sin\theta| = \sqrt{2}\sin\!\left(|\theta'| + \tfrac{\pi}{4}\right)

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

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

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

做仿射变换

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

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

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

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

\frac{\mathrm{dis1}}{\mathrm{dis2}} = \sqrt{2} \cdot \frac{\max(|\Delta u|, |\Delta v|)}{\sqrt{\Delta u^2 + \Delta v^2}}

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

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

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

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

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

证明（中值不等式）：取三点 $i, k, j$ 满足 $v_i < v_k < v_j$ 。记 $s_{ab} = (u_b - u_a) / (v_b - v_a)$ 。则

s_{ij} = \frac{(u_k - u_i) + (u_j - u_k)}{(v_k - v_i) + (v_j - v_k)}

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

\min(s_{ik}, s_{kj}) \le s_{ij} \le \max(s_{ik}, s_{kj})

故 $|s_{ij}| \le \max(|s_{ik}|, |s_{kj}|)$ 。

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

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

第 4 步：完整算法

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

按 $u = x + y$ 升序排，遍历相邻对更新最大比值
按 $v = x - y$ 升序排，遍历相邻对更新最大比值
两次累计的最大值就是答案

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

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| \le 10^9$ ， $dx^2 + dy^2 \le 8 \times 10^{18}$ 卡在 long long 上界 $9.2 \times 10^{18}$ 内，不会爆 ll。要稳一点 __int128_t 兜底也行
全程用 long double 配 sqrtl 保精度， cout << fixed << setprecision(12) 输出
多组 $T \le 10^5$ ， ios::sync_with_stdio(false) 必须关掉缓冲

📎 动画与源码

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

方向决定比值 ：拖一个点看比值随方向变化，验证"只看方向不看长度"
$xy$ ↔ $uv$ 双视图：直观看到 $\pm 45^\circ$ 方向变 $u, v$ 轴的几何过程
中值不等式三点 demo ：拖中间点 $k$ 的 $u$ 坐标，看 $s_{ij}$ 永远夹在 $s_{ik}, s_{kj}$ 之间
主算法 6 点演示 ：Step / Auto-play 走完两阶段排序 + 邻点扫，最优对正好在 P1-P2（u 都等于 7，Δu = 0，方向沿 v 轴 → 比值取到 $\sqrt{2}$ 上限）

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

AC 代码

AC 提交 — vjudge solution 69896828

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

Point::normL1() / Point::normLinf() 两个成员（曼哈顿 / 切比雪夫范数）
distancePP / distancePPL1 / distancePPLinf 三个自由函数（开方欧氏 / 曼哈顿 / 切比雪夫距离）

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

展开完整 C++ 源码（含几何模板 + Solve，约 970 行）

// teamname: Gospel_rock
/**
 * Problem: 距离之比
 * Contest: Gym
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/Gym-105158D#author=user:788193
 * Created: 2026-05-15 11:12:55
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define fsp(x) fixed<<setprecision(x)

using namespace std;

#if 1 && defined(LOCAL)
// @formatter:off
namespace DBG {
	template<typename T> void debug(T x);
	void debug(bool x);
	void debug(string x);
	template<typename T> void debug(vector<T> v);
	template<typename T, size_t N> void debug(array<T, N> v);
	template<typename T> void debug(set<T> s);
	template<typename T, typename U> void debug(pair<T, U> p);
	template<typename T, typename U> void debug(map<T, U> m);
	template<typename, typename = void> constexpr bool _has_iter_v = false;
	template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
	template<typename T>
	void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
	template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
	template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
	template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
	template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
	template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
	void _dbg() { cerr << endl; }
	template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
// @formatter:on
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr<<"\n---------------------------------------------------\n"
#define cEnd cerr<<"\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 * 2026-2-3  增加编译器识别 Real 类型功能
 * 2026-3-19 增加了从斜率式和一般式构造 Line
 * 2026-5-4  几何模板大改（QOJ 784 沉淀）：新增 isqrt / sqrtL、cross 三参数重载、polygonSignedArea，reorder_polygon 整体判向，isConvex 加 strict 参数，新增凸多边形直径旋转卡壳
 * 2026-5-5  Luogu P16223 沉淀：Point 加 id 字段，convex_diameter 加 n <= 2 退化特判，新增 furthest_pair_of_point
 * 2026-5-6  P3187 沉淀：getintersect 加浮点 assert + 显式 (DB) cross，make_convex_hull 加 strict 参数，新增 minimum_rectangle_cover
 * 2026-5-11 几何全面模板化：Point / Line 改 template<class T>，T 自动分流 ll / i128 / DB
 * 2026-5-12 加入了 Circle 类
 * 2026-5-13 加入了 half_plane_cut 和 unique_line_polar_angle_sort，加入了隐式转换和转换方向
 * 2026-5-15 加入了 HullMode
 * 2026-5-15 Point 加 normL1 / normLinf 成员, 新增 distancePP (L2 sqrt 版) / distancePPL1 (曼哈顿) / distancePPLinf (切比雪夫) 三个自由函数
 */

// floor(sqrt(n)), n >= 0；二分 + 防溢出
i128 isqrt(i128 n) {
	if (n <= 0) return 0;
	i128 lo = 0, hi = (i128) 2e18; // sqrt(4e36) <= 2e18
	while (lo < hi) {
		i128 mid = lo + (hi - lo + 1) / 2;
		if (mid <= n / mid) lo = mid; // 等价 mid*mid <= n，避免 i128 平方溢出
		else hi = mid - 1;
	}
	return lo;
}

// 统一 sqrt 入口：浮点直接 sqrtl；整数（含 i128）走 isqrt + fraction，避免 (long double) i128 在 n > 2^53 时丢整数精度。
template<typename T>
long double sqrtL(T n) {
	if constexpr (is_floating_point_v<T>) {
		return sqrtl((long double) n);
	} else {
		i128 ni = (i128) n;
		if (ni <= 0) return 0;
		i128 i = isqrt(ni);
		long double id = (long double) i;
		long double rd = (long double) (ni - i * i);
		// sqrt(i^2 + r) = i * sqrt(1 + r/i^2)
		return id * sqrtl(1.0L + rd / (id * id));
	}
}

template<class T>
int sgn(T x) {
	if (-eps < x && x < eps) return 0;
	return x < 0 ? -1 : 1;
}

// From → To 无损 promotion (ll → DB 通; DB → ll 禁)
// 这个不仅是为了无损，也是为了这个确保隐式转换方向不模糊
template<class From, class To>
inline constexpr bool is_promotion_v =
		is_arithmetic_v<From> && is_arithmetic_v<To> && !is_same_v<From, To> && (
			(is_integral_v<From> && is_floating_point_v<To>) ||
			(is_integral_v<From> && is_integral_v<To> && sizeof(From) <= sizeof(To)) ||
			(is_floating_point_v<From> && is_floating_point_v<To> && sizeof(From) <= sizeof(To))
		);

template<class T>
struct Point {
	T x, y;
	int id = -1; // 原始下标. -1 表示派生点 (+ - * 等算术结果) 或未赋值, id 无意义

	explicit Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {
	}

	// Point<U> → Point<T> 隐式 (仅 promotion 方向)
	template<class U, enable_if_t<is_promotion_v<U, T>, int> = 0>
	Point(const Point<U> &o) : x((T) o.x), y((T) o.y), id(o.id) {
	}

	// 只对左值生效的复合运算符
	Point &operator+=(Point p) & {
		x += p.x, y += p.y;
		return *this;
	}

	Point &operator-=(Point p) & {
		x -= p.x, y -= p.y;
		return *this;
	}

	Point &operator*=(T t) & {
		x *= t, y *= t;
		return *this;
	}

	Point &operator/=(T t) & {
		x /= t, y /= t;
		return *this;
	}

	Point operator-() const { return Point(-x, -y); }

	friend Point operator+(Point a, Point b) { return a += b; }
	friend Point operator-(Point a, Point b) { return a -= b; }
	friend Point operator*(Point a, T b) { return a *= b; }
	friend Point operator*(T a, Point b) { return b *= a; }
	friend Point operator/(Point a, T b) { return a /= b; }

	friend bool operator<(Point a, Point b) {
		int sx = sgn(a.x - b.x);
		if (sx != 0) return a.x < b.x;
		return a.y < b.y;
	}

	friend bool operator>(Point a, Point b) { return b < a; }

	friend bool operator==(Point a, Point b) {
		return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
	}

	friend bool operator!=(Point a, Point b) { return !(a == b); }

	friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
	friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }

	auto norm() const {
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t) x * x + (__int128_t) y * y;
		} else {
			return x * x + y * y;
		}
	}

	DB abs() const { return sqrtL(norm()); }

	// L1 范数 (曼哈顿) = |x| + |y|. 整型分支走 __int128_t 防溢出.
	auto normL1() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t) ax + (__int128_t) ay;
		} else {
			return ax + ay;
		}
	}

	// Linf 范数 (切比雪夫) = max(|x|, |y|). 返回类型与 T 同.
	T normLinf() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		return ax > ay ? ax : ay;
	}
};

template<class T>
auto cross(Point<T> a, Point<T> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	//（改为这个非float，那么在类型为I128时，仍然可以计算）
	if constexpr (!is_floating_point_v<T>) {
		return (__int128_t) a.x * b.y - (__int128_t) a.y * b.x;
	} else {
		return a.x * b.y - a.y * b.x;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) × (b - o)
// 用途: 判 3 点 turn (>0 左转, <0 右转, =0 共线) / 2 倍三角形有向面积 / 凸包面积扫描
template<class T>
auto cross(Point<T> o, Point<T> a, Point<T> b) {
	return cross(a - o, b - o);
}

template<class T, class U>
auto dot(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t) a.x * b.x + (__int128_t) a.y * b.y;
	} else {
		return a.x * b.x + a.y * b.y;
	}
}

// 采用两点式
template<class T>
struct Line {
	Point<T> p1, p2;

	Line() = default;

	Line(Point<T> a, Point<T> b) : p1(a), p2(b) {
	}

	// Line<U> → Line<T> 隐式 (仅 promotion 方向)
	template<class U, enable_if_t<is_promotion_v<U, T>, int> = 0>
	Line(const Line<U> &o) : p1(o.p1), p2(o.p2) {
	}

	// AC https://qoj.ac/submission/2146870
	Line(T k, T c) : p1(Point<T>(0, c)), p2(Point<T>(1, k + c)) {
	}

	friend bool operator<(Line a, Line b) {
		if (a.p1 != b.p1) return a.p1 < b.p1;
		return a.p2 < b.p2;
	}

	friend bool operator==(Line a, Line b) {
		if (a.p1 != b.p1) return false;
		if (a.p2 != b.p2) return false;
		return true;
	}

	friend istream &operator>>(istream &is, Line &e) {
		T a, b, c, d;
		is >> a >> b >> c >> d;
		e = Line(Point<T>(a, b), Point<T>(c, d));
		return is;
	}

	friend ostream &operator<<(ostream &os, Line l) {
		return os << "<" << l.p1 << ", " << l.p2 << ">";
	}
};

Line<DB> gen_line_from_general(DB a, DB b, DB c) {
	// 方向向量 (b, -a)
	Point<DB> p1, p2;
	if (b != 0) {
		p1 = Point<DB>(0, -c / b);
	} else {
		p1 = Point<DB>(-c / a, 0);
	}
	p2 = Point<DB>(p1.x + b, p1.y - a);
	return Line<DB>(p1, p2);
}

// 使用这个东西，Point 必须是 double 等浮点类型
template<class T, class U>
Point<DB> project(Point<T> p, Line<U> l) {
	Point<DB> vec = l.p2 - l.p1;
	//                        这个距离反正早除晚除都要除掉
	DB r = dot(vec, p - l.p1) / ((DB) vec.x * vec.x + vec.y * vec.y);
	return l.p1 + vec * r;
}

template<class T>
Point<T> reflect(Point<T> p, Line<T> l) {
	Point<T> proj = project(p, l);
	return proj + proj - p;
}

mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

constexpr int ON_SEGMENT = 0;
constexpr int COUNTER_CLOCKWISE = 1;
constexpr int CLOCKWISE = -1;
constexpr int ONLINE_BACK = 2;
constexpr int ONLINE_FRONT = -2;

template<class T, class U>
int CCW(Point<T> p, Line<U> l) {
	Point<DB> a = l.p2 - l.p1;
	Point<DB> b = p - l.p1;
	if (sgn(cross(a, b)) > 0) {
		return COUNTER_CLOCKWISE;
	}
	if (sgn(cross(a, b)) < 0) {
		return CLOCKWISE;
	}
	if (sgn(dot(a, b)) < 0) {
		return ONLINE_BACK;
	}
	if (a.norm() < b.norm()) return ONLINE_FRONT;
	return ON_SEGMENT;
}

template<class T>
bool isOrthogonal(Line<T> a, Line<T> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(dot(c, d));
}

template<class T>
bool isParallel(Line<T> a, Line<T> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(cross(c, d));
}

template<class T>
bool isSegIntersect(Line<T> a, Line<T> b) {
	// 判断线段相交
	return CCW(b.p1, a) * CCW(b.p2, a) <= 0 && CCW(a.p1, b) * CCW(a.p2, b) <= 0;
}

// bool isIntersectStrict(Line a,Line b){    // 判断线段相交
//     return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0     (利用叉乘乘以自身为0，消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式  拿到的是两直线交点
template<class T>
Point<DB> getintersect(const Line<T> &a, const Line<T> &b) {
	Point<DB> p = a.p1, v = a.p2 - a.p1, q = b.p1, w = b.p2 - b.p1;
	Point<DB> u = p - q;
	DB t = (DB) cross(w, u) / cross(v, w);
	return p + v * t;
}

template<class T>
auto distancePPNorm(const Point<T> &a, const Point<T> &b) {
	return (a - b).norm();
}

// L2 欧几里得距离 (sqrt 版, 用 long double). 整型坐标走 isqrt + fraction 不丢精度.
template<class T>
DB distancePP(const Point<T> &a, const Point<T> &b) {
	return (a - b).abs();
}

// L1 曼哈顿距离 = |dx| + |dy|. 返回类型继承 normL1 (整型 -> __int128_t, 浮点 -> T).
template<class T>
auto distancePPL1(const Point<T> &a, const Point<T> &b) {
	return (a - b).normL1();
}

// Linf 切比雪夫距离 = max(|dx|, |dy|). 返回类型 T.
template<class T>
T distancePPLinf(const Point<T> &a, const Point<T> &b) {
	return (a - b).normLinf();
}

// 也可以用 project 来算
template<class T>
DB distancePL(Point<T> p, Line<T> l) {
	auto val = cross(l.p1, l.p2, p);
	return sgn(val) * val / (l.p2 - l.p1).abs();
}

// AC https://qoj.ac/submission/2001668
template<class T>
DB distancePS(Point<T> p, Line<T> l) {
	// 避免 distanceSS 调用的时候发生这个退化（即线段退化为了点）
	if (l.p1 == l.p2) {
		return (p - l.p1).abs();
	}
	auto t = l.p2 - l.p1;
	if (sgn(dot(t, p - l.p1)) < 0) {
		return (p - l.p1).abs();
	}
	if (sgn(dot(t, p - l.p2)) > 0) {
		return (p - l.p2).abs();
	}
	return distancePL(p, l);
}

// AC https://qoj.ac/submission/2001588
template<class T>
DB distanceSS(Line<T> a, Line<T> b) {
	if (isIntersect(a, b)) return 0;
	return min({distancePS(a.p1, b), distancePS(a.p2, b), distancePS(b.p1, a), distancePS(b.p2, a)});
}

// 多边形 2 倍有向面积 (不除 2 以保持整数精度).
// 返回类型 auto 自动跟 cross 走 (整数 Real → i128, 浮点 Real → Real).
// > 0: CCW; < 0: CW; == 0: 退化 (全共线 / 自交).
// 用途: polygonArea (取 abs / 2 得真面积) / reorder_polygon (取符号判方向).
template<class T>
auto polygonSignedArea(const vector<Point<T> > &poly) {
	auto res = cross(Point<T>(), Point<T>()); // 零值, 类型由 cross 继承
	size_t n = poly.size();
	for (size_t i = 0; i < n; ++i) {
		res += cross(poly[i], poly[(i + 1) % n]);
	}
	return res;
}

template<class T>
DB polygonArea(const vector<Point<T> > &poly) {
	auto s = polygonSignedArea(poly);
	if (s < 0) s = -s;
	return (DB) s / 2.0;
}

// 求周长
template<class T>
DB polygon_perimeter(const vector<Point<T> > &poly) {
	DB res = 0;
	size_t n = poly.size();
	for (int i = 0; i < n; ++i) {
		res += (poly[i] - poly[(i + 1) % n]).abs();
	}
	return res;
}

// 正 n 边形面积: A = n * l^2 / (4 * tan(pi / n)), n >= 3
DB regular_polygon_area(ll n, DB l) {
	return (DB) n * l * l / (4.0L * tanl(PI / (DB) n));
}

// ===== 圆 (Circle) =====
//
// 圆心 c + 半径 r. 配套测度五件套 (弧长 / 弦长 / 弓形高 / 扇形面积 / 弓形面积).
// 入参 theta 是弦所对的圆心角 (弧度), theta ∈ [0, 2π]:
//   theta < π → minor 弓形 (小的那块); theta > π → major 弓形 (大的那块).
//   公式同一个, 不做角度 ↔ 弧度转换 (调用方自己 deg * PI / 180).
template<class T>
struct Circle {
	Point<T> c;
	T r;

	Circle() = default;

	Circle(Point<T> c_, T r_) : c(c_), r(r_) {
	}

	// 圆上极角 theta 处的点: c + (r cos theta, r sin theta)
	// theta 不限定范围 (允许负值 / > 2π), 始终走 cos/sin 不抛 assert
	Point<DB> point_at(DB theta) const {
		return Point<DB>((DB) c.x + (DB) r * cosl(theta),
		                 (DB) c.y + (DB) r * sinl(theta));
	}

	void check_theta(DB theta) const {
#ifdef LOCAL
		assert(theta >= -eps && theta <= 2 * PI + eps);
#endif
		(void) theta;
	}

	DB arc_length(DB theta) const {
		check_theta(theta);
		return (DB) r * theta;
	}

	DB chord_length(DB theta) const {
		check_theta(theta);
		return 2.0L * (DB) r * sinl(theta / 2);
	}

	// 弓形高 (sagitta) = r (1 - cos(theta / 2))
	DB sagitta(DB theta) const {
		check_theta(theta);
		return (DB) r * (1.0L - cosl(theta / 2));
	}

	// 扇形面积 = (1/2) r^2 theta
	DB sector_area(DB theta) const {
		check_theta(theta);
		return 0.5L * (DB) r * r * theta;
	}

	// 弓形面积 = (1/2) r^2 (theta - sin theta)
	// AC https://vjudge.net/solution/69814399 (Area of the Devil)
	DB segment_area(DB theta) const {
		check_theta(theta);
		return 0.5L * (DB) r * r * (theta - sinl(theta));
	}
};

// 从极角 theta_from CCW 转到 theta_to 的弧度差, 始终落在 [0, 2π).
// 用途: 圆周上 from -> to 的逆时针弧角 (segment_area / arc_length 入参).
// 注意: 这是有向差, 不是 abs(theta_to - theta_from) —— 后者在 wrap 处 (例如
//   from = 352°, to = 54°) 会算成 298° 而非真实的 62°.
static DB ccw_angle(DB theta_from, DB theta_to) {
	DB d = std::fmod(theta_to - theta_from, 2 * PI);
	if (d < 0) d += 2 * PI;
	return d;
}

// 按照逆时针方向整齐排列
template<class T>
void reorder_polygon(vector<Point<T> > &poly) {
	ll n = poly.size();
	// 用 polygonSignedArea 判方向, 不依赖局部前三点 cross
	// (含共线点的 polygon 在前三点共线时, 局部判方向会误判为 CW)
	if (sgn(polygonSignedArea(poly)) < 0) {
		reverse(poly.begin(), poly.end());
	}
	// 找到字典序最小的点
	ll pos_mn = 0;
	for (int i = 1; i < n; ++i) {
		if (poly[i] < poly[pos_mn]) {
			pos_mn = i;
		}
	}
	// Performs a left rotation on a range of elements
	// 向左循环移动，把 pos_mn 移动到第一个 [0]
	rotate(poly.begin(), poly.begin() + pos_mn, poly.end());
}

// 不允许自交的多边形，顺序都可以，会把 poly 变为 CCW 顺序（逆时针）
// AC https://qoj.ac/submission/2002121
// strict = true:  严格凸 (拒绝三点共线 / 内角 = 180°)
// strict = false: 弱凸    (允许三点共线 / 内角 = 180°), 题面允许共线时用
template<class T>
bool isConvex(vector<Point<T> > poly, bool strict) {
	ll n = poly.size();
	if (n <= 2) return false;
	reorder_polygon(poly);
	auto fail = [&](int s) { return strict ? s <= 0 : s < 0; };
	// 在一个标准的凸多边形中，如果我们站在最左下角的点（poly[0]）往外看
	// 其他所有顶点 poly[1], poly[2], ..., poly[n-1] 应该按照逆时针方向整齐排列。
	// 从而排除星形（自交）多边形和乱序点集。
	bool has_turn = false; // 至少一处真左转, 排除全共线 (面积 = 0) 退化
	for (int i = 1; i < n - 1; ++i) {
		int s = sgn(cross(poly[0], poly[i], poly[i + 1]));
		if (fail(s)) return false;
		if (s > 0) has_turn = true;
	}
	// 弱凸模式下还需 has_turn: 否则 N 点全共线时上面两个循环 cross 全 0,
	// 误把"线段"判成多边形 (strict 模式 has_turn 在第一个循环必然为 true)
	if (!has_turn) return false;
	// 判断单个内角是否 ≥ 180。
	for (int i = 0; i < n; ++i) {
		ll i1 = (i + 1) % n, i2 = (i + 2) % n;
		auto a = poly[i1] - poly[i], b = poly[i2] - poly[i1];
		// strict 时拒绝内角 = 180 (sgn = 0); 弱凸允许 (只拒绝凹: sgn < 0)
		if (fail(sgn(cross(a, b)))) {
			return false;
		}
	}
	return true;
}

// 2 是包含，1是在线上，0是出界
template<class T>
int isInPolygon(Point<T> p, const vector<Point<T> > &poly) {
	ll res = 0;
	Line<T> l(p, p + Point<T>(2e5, rng()));
	for (int i = 0; i < poly.size(); ++i) {
		int i1 = (i + 1) % SZ(poly);
		Line<T> seg = Line<T>(poly[i], poly[i1]);
		int ccw = CCW(p, seg);
		if (ccw == ON_SEGMENT) {
			return 1;
		}
		if (isIntersect(l, seg)) {
			++res;
		}
	}
	// 奇偶法则，多边形内点的射线一定只会经过奇数条边。
	if (res & 1) return 2;
	return 0;
}

// 定义获取区域的辅助函数，辅助
template<class T>
int get_part_of_point(const Point<T> &p) {
	if (p.y < 0) return 0; // 下半平面 (-pi, 0)
	if (p.y == 0 && p.x >= 0) return 1; // 角度为 0 的部分 (含原点)
	return 2; // 上半平面 (0, pi]
}

// 你需要将所有点按照 atan2(yi,xi)进行排序，也即从 x 轴负半轴（不含）开始进行逆时针排序。
// AC https://qoj.ac/submission/2001485
template<class T>
void polar_angle_sort(vector<Point<T> > &poly) {
	sort(poly.begin(), poly.end(), [](const Point<T> &a, const Point<T> &b)-> bool {
		int part1 = get_part_of_point(a), part2 = get_part_of_point(b);
		if (part1 != part2) {
			return part1 < part2;
		}
		return sgn(cross(a, b)) == 1;
	});
}

// 重载，用来完成这个对线的极角排序，用于这个半平面交
template<class T>
void polar_angle_sort(vector<Line<T> > &poly) {
	sort(poly.begin(), poly.end(), [](const Line<T> &al, const Line<T> &bl)-> bool {
		auto a = al.p2 - al.p1, b = bl.p2 - bl.p1;
		int part1 = get_part_of_point(a), part2 = get_part_of_point(b);
		if (part1 != part2) {
			return part1 < part2;
		}
		int c = sgn(cross(a, b));
		if (c != 0) return c == 1;
		// bl 在 al 的 右侧，因此 al 应该排在前面（返回 true）
		return CCW(bl.p1, al) == CLOCKWISE;
	});
}

template<class T>
void unique_line_polar_angle_sort(vector<Line<T> > &poly) {
	polar_angle_sort(poly);
	poly.resize(unique(all(poly), [](const Line<T> &al, const Line<T> &bl) {
		auto a = al.p2 - al.p1, b = bl.p2 - bl.p1;
		if (sgn(cross(a, b)) == 0) {
			return true;
		}
		return false;
	}) - poly.begin());
}

// 两个小凸包，合成一个大凸包，这个大凸包，即闵可夫斯基和
// 参考了 https://github.com/hh2048/XCPC 的 mincowski
// minkowski 的减法就是加上关于原点的中心对称图形
// AC https://qoj.ac/submission/2002545
template<class T>
vector<Point<T> > minkowski(vector<Point<T> > &P1, vector<Point<T> > &P2) {
	reorder_polygon(P1);
	reorder_polygon(P2);
	int n = P1.size(), m = P2.size();
	vector<Point<T> > V1(n), V2(m);
	// 预处理：计算差分向量（边向量）
	for (int i = 0; i < n; i++) {
		V1[i] = P1[(i + 1) % n] - P1[i];
	}
	for (int i = 0; i < m; i++) {
		V2[i] = P2[(i + 1) % m] - P2[i];
	}
	vector<Point<T> > ans = {P1.front() + P2.front()};
	int t = 0, i = 0, j = 0;
	while (i < n && j < m) {
		// cross(V1,V2)> 0，就说明 V1 小于这个 V2(在 CCW 下)
		// 所以先选择这个小的 V1，反之同理
		Point<T> val = sgn(cross(V1[i], V2[j])) > 0 ? V1[i++] : V2[j++];
		ans.push_back(ans.back() + val);
	}
	// 处理剩余的边
	while (i < n) ans.push_back(ans.back() + V1[i++]);
	while (j < m) ans.push_back(ans.back() + V2[j++]);
	return ans;
}


enum HullMode { HULL_FULL, HULL_LOWER, HULL_UPPER };

// strict = true:  严格凸包 (不保留三点共线的中间点)
// strict = false: 弱凸包    (保留三点共线的中间点), 题目要求"凸包上所有点"时用
template<class T>
vector<Point<T> > make_convex_hull(vector<Point<T> > A, bool strict, HullMode hull_mode) {
	size_t n = A.size();
	if (n <= 2) {
		// 特判
		return A;
	}
	vector<Point<T> > ans(n * 2);
	// Andrew 算法的核心：先按 X 坐标排序，X 相同按 Y 坐标排序
	// 这样我们就可以保证处理点的顺序是从左到右
	sort(A.begin(), A.end());
	// strict 时 cross == 0 共线也弹; 弱凸只在 cross < 0 凹陷时弹
	auto fail = [&](ll s) { return strict ? s >= 0 : s > 0; };
	int now = -1;
	for (int i = 0; i < n; i++) {
		// 维护下凸包
		while (now > 0 && fail(sgn(cross(A[i], ans[now], ans[now - 1])))) {
			now--; // 弹出栈顶，因为它会导致凹陷 (strict 时还会弹掉共线)
		}
		ans[++now] = A[i];
	}
	if (hull_mode == HULL_LOWER) {
		ans.resize(now + 1);
		return ans;
	}
	int pre = now;
	// 从右向左扫描所有点（注意是从 n-2 开始，因为 n-1 已经在栈顶了）
	for (int i = n - 2; i >= 0; i--) {
		// 维护上凸包
		while (now > pre && fail(sgn(cross(A[i], ans[now], ans[now - 1])))) {
			now--;
		}
		ans[++now] = A[i];
	}
	if (hull_mode == HULL_UPPER) {
		return vector<Point<T> >(ans.begin() + pre, ans.begin() + now + 1);
	}
	ans.resize(now);
	return ans;
}

// 以逆时针顺序给定一个 n 个点的凸多边形（可能存在三点共线），求它的直径。
// AC https://qoj.ac/submission/2321607
template<class T>
long double convex_diameter(const vector<Point<T> > &A) {
#ifdef LOCAL
	vector<Point<T> > B(all(A));
	assert(isConvex(B,false));
#endif
	// 退化特判
	if (SZ(A) <= 1) return 0;
	if (SZ(A) == 2) return sqrtL(distancePPNorm(A[0], A[1]));
	// A = make_convex_hull(A);
	auto ans = distancePPNorm(A[0], A[0]);
	auto area = [&](ll l, ll r) {
		auto res = cross(A[r], A[(r + 1) % SZ(A)], A[l]);
		if (res < 0) res = -res;
		return res;
	};
	auto need_l_move = [&](ll l, ll r) -> bool {
		if (area(l, r) <= area((l + 1) % SZ(A), r)) {
			return true;
		}
		return false;
	};
	// l 是这个我们的点，r 是我们的这个边
	for (int l = 0, r = 0; r < SZ(A); ++r) {
		while (need_l_move(l, r)) {
			l = (l + 1) % SZ(A);
		}
		ans = max(ans, distancePPNorm(A[l], A[r]));
		ans = max(ans, distancePPNorm(A[l], A[(r + 1) % SZ(A)]));
	}
	return sqrtL(ans);
}

// AC https://www.luogu.com.cn/record/276669701
template<class T>
pair<int, int> furthest_pair_of_point(vector<Point<T> > A) {
	A = make_convex_hull(A, true, HULL_FULL);
	// 退化特判
	if (SZ(A) == 1) return {A[0].id, A[0].id};
	if (SZ(A) == 2) return {A[0].id, A[1].id};
	decltype(distancePPNorm(A[0], A[0])) ans = 0;
	auto area = [&](ll l, ll r) {
		auto res = cross(A[r], A[(r + 1) % SZ(A)], A[l]);
		if (res < 0) res = -res;
		return res;
	};
	auto need_l_move = [&](ll l, ll r) -> bool {
		if (area(l, r) <= area((l + 1) % SZ(A), r)) {
			return true;
		}
		return false;
	};
	// l 是这个我们的点，r 是我们的这个边
	pair<int, int> ans_pair;
	for (int l = 0, r = 0; r < SZ(A); ++r) {
		while (need_l_move(l, r)) {
			l = (l + 1) % SZ(A);
		}
		if (distancePPNorm(A[l], A[r]) > ans) {
			ans = distancePPNorm(A[l], A[r]);
			ans_pair = {A[l].id, A[r].id};
		}
		int rn = (r + 1) % SZ(A);
		if (distancePPNorm(A[l], A[rn]) > ans) {
			ans = distancePPNorm(A[l], A[rn]);
			ans_pair = {A[l].id, A[rn].id};
		}
	}
	return ans_pair;
}

// 最小矩形覆盖：返回 {面积, 4 个矩形顶点（以底边 BL 起、CCW）}
// 前置：T = DB（reconstruct 走 getintersect 必须浮点）
// AC https://www.luogu.com.cn/record/276877086
pair<DB, array<Point<DB>, 4> > minimum_rectangle_cover(vector<Point<DB> > A) {
	A = make_convex_hull(A, true, HULL_FULL);
	int n = SZ(A);
	auto e_of = [&](int i) { return A[(i + 1) % n] - A[i]; }; // 第 i 条凸包边的方向向量
	int up = 0, l = 0, r = 0;
	using Type = decltype(dot(A[0], A[0]));
	Type mn_area = 0;
	do {
		auto e0 = e_of(0);
		for (int i = 0; i < SZ(A); ++i) {
			// 同一个底，面积越大，高自然越大
			if (cross(e0, A[i] - A[0]) > cross(e0, A[up] - A[0])) {
				up = i;
			}
			if (dot(e0, A[i] - A[0]) > dot(e0, A[r] - A[0])) {
				r = i;
			}
			if (dot(e0, A[i] - A[0]) < dot(e0, A[l] - A[0])) {
				l = i;
			}
		}
		auto w = dot(e0, A[r] - A[l]);
		auto h = cross(e0, A[up] - A[0]);
		mn_area = w * h;
	} while (false);
	int bestL = l, bestR = r, bestE = 0, bestUp = up;
	for (int edge = 0; edge < SZ(A); ++edge) {
		Point<DB> e = e_of(edge);
		while (cross(e, A[(up + 1) % SZ(A)] - A[edge]) > cross(e, A[up] - A[edge]))
			up = (up + 1) % SZ(A);
		while (dot(e, A[(r + 1) % SZ(A)] - A[edge]) > dot(e, A[r] - A[edge]))
			r = (r + 1) % SZ(A);
		while (dot(e, A[(l + 1) % SZ(A)] - A[edge]) < dot(e, A[l] - A[edge]))
			l = (l + 1) % SZ(A);
		// 这个宽和高均乘以了 e 的长度
		auto w = dot(e, A[r] - A[l]);
		auto h = cross(e, A[up] - A[edge]);
		auto area = w * h;
		if (area * e_of(bestE).norm() < mn_area * e.norm()) {
			mn_area = area;
			// mn_area_edge = e.norm();
			tie(bestL, bestR, bestE, bestUp) = make_tuple(l, r, edge, up);
		}
	}
	// 还原 4 顶点 = 4 条切线两两相交（4 条线方向：底/顶 ∥ e；左/右 ∥ e^⊥）
	Point e = e_of(bestE);
	Point e_perp(-e.y, e.x); // CCW 90° 旋转
	Line bottom(A[bestE], A[bestE] + e);
	Line top_(A[bestUp], A[bestUp] + e);
	Line right_(A[bestR], A[bestR] + e_perp);
	Line left_(A[bestL], A[bestL] + e_perp);
	array<Point<DB>, 4> corners = {
		getintersect(bottom, left_), // BL
		getintersect(bottom, right_), // BR
		getintersect(top_, right_), // TR
		getintersect(top_, left_), // TL
	};
	return {(long double) mn_area / e.norm(), corners};
}

// AC https://vjudge.net/solution/69843663
template<class T>
vector<Point<DB> > half_plane_cut(vector<Line<T> > lines) {
	unique_line_polar_angle_sort(lines);
	deque<Line<T> > q;
	for (auto l: lines) {
		if (SZ(q) < 2) {
			q.push_back(l);
			continue;
		}
		auto checkBack = [&]() {
			auto p = getintersect(q.rbegin()[0], q.rbegin()[1]);
			if (CCW(p, l) != CLOCKWISE) return true;
			return false;
		};
		while (SZ(q) >= 2 && !checkBack()) {
			q.pop_back();
		}
		auto checkFront = [&]() {
			auto p = getintersect(q.begin()[0], q.begin()[1]);
			if (CCW(p, l) != CLOCKWISE) return true;
			return false;
		};
		while (SZ(q) >= 2 && !checkFront()) {
			q.pop_front();
		}
		q.push_back(l);
	}
	// wrap-around: 用队首线再清一遍队尾
	while (SZ(q) >= 3) {
		auto p = getintersect(q.rbegin()[0], q.rbegin()[1]);
		if (CCW(p, q.front()) != CLOCKWISE) break;
		q.pop_back();
	}
	// 对称地: 用队尾线再清一遍队首 (有的写法会加, 多数情况下前面 checkFront 已经清干净, 但保险起见)
	while (SZ(q) >= 3) {
		auto p = getintersect(q.begin()[0], q.begin()[1]);
		if (CCW(p, q.back()) != CLOCKWISE) break;
		q.pop_front();
	}
	if (SZ(q) < 3) return {};
	vector<Point<DB> > poly;
	for (int i = 0; i < SZ(q); ++i) {
		auto p = getintersect(q[i], q[(i + 1) % SZ(q)]);
		poly.push_back(p);
	}
	return poly;
}

void Solve() {
	ll N;
	cin >> N;
	vector<Point<ll> > A(N);
	for (auto &p: A) {
		cin >> p;
	}
	sort(all(A), [](const Point<ll> &aO, const Point<ll> &bO) {
		Point<ll> a(aO.x + aO.y, aO.x - aO.y), b(bO.x + bO.y, bO.x - bO.y);
		return a < b;
	});
	DB ans = 0;
	for (int i = 0; i < SZ(A); ++i) {
		DB lans = (DB) distancePPL1(A[i], A[(i + 1) % SZ(A)]) / distancePP(A[i], A[(i + 1) % SZ(A)]);
		ans = max(ans, lans);
	}
	sort(all(A), [](const Point<ll> &aO, const Point<ll> &bO) {
		Point<ll> a(aO.x + aO.y, aO.x - aO.y), 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 < SZ(A); ++i) {
		DB lans = (DB) distancePPL1(A[i], A[(i + 1) % SZ(A)]) / distancePP(A[i], A[(i + 1) % SZ(A)]);
		ans = max(ans, lans);
	}
	cout << fsp(12) << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*
AC
https://vjudge.net/solution/69896828

*/

心路历程

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

看到 $\mathrm{dis1} / \mathrm{dis2}$ 直觉就反应"这跟方向有关"，写成 $|\cos\theta| + |\sin\theta|$ 后就锁死"找最接近 $\pm 45^\circ$ 方向的点对"
但是 $O(n^2)$ 枚举显然不行（ $\sum n = 2 \cdot 10^5$ ），第一反应想凸包——结论：凸包做不了。反例：最优对可以在凸包内部。比如三角形 $A = (0, 0), B = (10, 10), C = (10, -10)$ 加两个内部点 $D = (5, 0), E = (5, 1)$ ， $D, E$ 的 $\Delta u = 0$ 比值直接 $\sqrt{2}$ 顶天，但 $D, E$ 都不在凸包上
直接看了官方题解才知道是中值不等式那一招。证明优美但"赛场上能不能想到"是另一回事——下次见到「对所有点对极大化方向相关量」类几何题先把这条工具拿出来用
实现时本来要在 Solve 里手写 L1 / L2 距离，顺手沉淀进几何模板（这次加了 distancePP / distancePPL1 / distancePPLinf 三个自由函数 + Point::normL1 / normLinf 两个成员），后续题目直接复用

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

附件

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

distance_ratio.html.txt

POJ 3608 - Bridge Across Islands

Posted on 2026-05-11

原题：POJ 3608 Bridge Across Islands（POJ 评测机太老仅 C++98，强烈推荐 vjudge 上的镜像 OpenJ_Bailian-3851）。本题是两凸多边形最近距离的旋转卡壳模板题，但有一个反直觉的「单调推进准则」选择 —— 第一版贪心在 OJ 上 TLE，调试改 cross 单调推进后又 WA，最终发现单次调用对偶覆盖不完整，必须 (A, B) 和 (B, A) 各跑一次。

题目大意

太平洋中央有一个王国，领土由两座岛屿组成，被洋流冲成两个凸多边形。国王要造一座桥连两岛，问两岛边界的最小距离是多少。

输入

多组测试用例。每组先给两整数 $N$ 和 $M$ ( $3 \le N, M \le 10000$ )，接下来 $N$ 行各给一对坐标描述第一个凸多边形的一个顶点（已按某种顺序给出，CW 或 CCW），再接 $M$ 行给第二个凸多边形顶点。坐标 $\in [-10000, 10000]$ 。

一行 $N = M = 0$ 表示输入结束。

输出

每组输出最小距离，误差 $\le 10^{-3}$ 。

样例

4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0

输出：

1.00000

思路讲解

一句话

两凸多边形最近距离 = 旋转卡壳 + facing 弧双指针 $O(N + M)$ ；推进准则用「cross(a, b') 角度差」、不要用「dis2 < dis1 顶点-边距离单峰」（贪心在背面弧会卡住）；最终结果必须 (A, B) 和 (B, A) 各调一次取 $\min$ 才覆盖完整。

把最近距离归并到「顶点 → 线段」

两个不相交的凸多边形之间，最小距离的实现位置只有三种：

特征对	是否独立	备注
顶点 - 边内部	✓ 主路径	从某顶点向另一多边形某条边作垂线，垂足落在边内
顶点 - 顶点	退化	当 $\mathrm{dist}(v_A,\ \mathrm{seg}(e_B))$ 的垂足落在 $e_B$ 外，点-线段距离自动退成点-点距离
边 - 边	退化	仅当两边平行才可能；端点也取得到，被「顶点对线段」覆盖

关键不变量：枚举所有 $(顶点,\ \mathrm{对面边})$ 对，算点-线段距离取 $\min$ ，三种情形一网打尽。

facing 弧 + 单调推进

固定 $A$ 上一个顶点 $p$ ，凸性下 $B$ 上「真正可能成为离 $p$ 最近的那条边」有且仅有一条 —— 称它为 $p$ 的 facing edge。形象点：从 $p$ 看过去， $B$ 朝向 $p$ 那半弧上正对 $p$ 的那条边，其它边要么被它挡住、要么转到背面去了。

把 $p$ 沿 $A$ 走 CCW 一圈，那条 facing 边在 $B$ 上的位置是**「短程单调、长程往返」**：

短程（ $p$ 走在 $A$ 朝 $B$ 那半弧上）：facing 边在 $B$ 上 单调推进（不回退）
长程（ $p$ 越过 $A$ 的背面弧）： $B$ 没有新边可选，facing 边只能沿同一段 facing 弧 退回来
整圈轨迹 = 「推过去 → 退回来」 = 往返

算法直接好处：两个指针不需要走完一整圈，各自只走完自己的 facing 弧就够了，总步数 $\le N + M$ 。

初始 facing pair：A 最低 + B 最高

按代码取：

$\texttt{eA}$ = $A$ 上 $y$ 最小的点的下标
$\texttt{eB}$ = $B$ 上 $y$ 最大的点的下标

几何上 $\texttt{eA}$ 看上去就是 $\texttt{eB}$ 、 $\texttt{eB}$ 看下去就是 $\texttt{eA}$ —— 这一对是初始 facing pair，也是 $A$ / $B$ 各自 facing 弧的一个端点。

不过这个初始只在「 $B$ 整体在 $A$ 上方」时直观对齐；其它分布下（ $A$ 在右、 $B$ 在左之类）yMnA + yMxB 不一定是真 facing pair。没关系 —— 推进准则用 cross 角度差驱动后，初始位置不正确也能在 $O(N + M)$ 步内追上正确的对踵 pair，所以这个朴素初始化就够了。

`cross(a, b')` 推进准则（核心）

设：

$\vec{a} = A_{i+1} - A_i$ ： $A$ 在 $A_i$ 的 CCW 出边方向
$\vec{b}' = B_j - B_{j+1}$ ： $B$ 在 $B_j$ 的 CCW 出边反向（因为 $B$ 的 facing 弧逆 $B$ 的 CCW 序前进）

推进准则：

\mathrm{cross}(\vec{a},\ \vec{b}') \quad \begin{cases} > 0 & \Rightarrow\ \mathtt{++i}\ \text{（推进 A）} \\ < 0 & \Rightarrow\ \mathtt{++j}\ \text{（推进 B）} \\ = 0 & \text{两个都试一下取 min} \end{cases}

几何意义：初始 facing pair 处 $\vec{a}$ 和 $\vec{b}'$ 都大约朝 $+x$ ，几乎平行同向；两者沿各自多边形 CCW 推进时都向 CCW 方向旋转（凸性）。 $\mathrm{cross}(\vec{a},\ \vec{b}')$ 衡量两者角度差：

$> 0$ ： $\vec{b}'$ 在 $\vec{a}$ 的 CCW 一侧 $\Rightarrow$ $\vec{a}$ 角度落后 $\Rightarrow$ 让 $A$ 推一步追上
$< 0$ ：反之，让 $B$ 推一步

为什么这样不会 TLE：每步刚好推一个指针、各自只能 forward。 $i$ 走完 $A$ 一圈、 $j$ 走完 $B$ 一圈就停，总步数 $\le N + M$ 。背面弧问题自动消失 —— cross 一直按角度差驱动，根本不依赖「dis 谁更小」这种局部贪心。

为什么必须 `(A, B)` + `(B, A)` 各调一次

单次 cal_min_dis_two_convex(A, B) 只覆盖**「 $A$ 顶点 → $B$ 边」**这组对偶配置 —— 也就是「枚举 $A$ 上每个顶点，找 $B$ 上对应的 facing 边」。

但反对称几何里答案可能取在另一边：细长 $A$ 戳向粗 $B$ 的边中间， $A$ 的端点垂足落在 $B$ 的边内部 —— 这种「 $A$ 顶点 - $B$ 边」抓得到；反过来「 $B$ 顶点 - $A$ 边」抓不到。

解决：把同一份代码以 (B, A) 参数顺序再跑一遍，补上反向对偶，最后两次取 $\min$ ：

`c++

DB ans = INFINITY;

ans = min(ans, cal_min_dis_two_convex(A, B));

ans = min(ans, cal_min_dis_two_convex(B, A));




漏一次会在 stress test 第 24 个 seed 翻车（**已实测**，反例见 `counterexample_seed24.html` 附件，期望 $62.29$ 实测 $63.7$ ）。

## 📎 动画与源码

- $\vec{a}$ / $\vec{b}'$ 向量 + `cross` 推进逐步演示：`cross_product_demo.html`（见附件）
- 单次调用对偶不完整反例：`counterexample_one_call_only.html`、`counterexample_seed24.html`

# AC 代码

[**AC 提交链接（vjudge OpenJ\_Bailian-3851）**](https://vjudge.net/solution/69793877)

核心函数：

// 两凸多边形最近距离（旋转卡壳, O(n + m)）

// 单次调用只覆盖「A 边 → B 顶点」配置，

// 调用方需以 (A, B) 和 (B, A) 各调一次取 min。

template

DB cal_min_dis_two_convex(vector<Point> A, vector<Point> B) {

reorder_polygon(A);

reorder_polygon(B);

ll yMnA = min_element(all(A), [](const Point<T> &a, const Point<T> &b) {

    return a.y < b.y;

}) - A.begin();

ll yMxB = max_element(all(B), [](const Point<T> &a, const Point<T> &b) {

    return a.y < b.y;

}) - B.begin();

DB ans = INFINITY;

ll eA = yMnA, eB = yMxB;

for (int _ = 0; _ < SZ(A) + SZ(B); ++_) {

    auto check = [&]() {

        auto vecA = A[(eA + 1) % SZ(A)] - A[eA];

        auto vecB = B[(eB + 1) % SZ(B)] - B[eB];

        return cross(vecA, vecB) > 0;

    };

    while (check()) ++eB, eB %= SZ(B);

    ans = min(ans, distanceSS(Line(A[(eA + 1) % SZ(A)], A[eA]),

                              Line(B[(eB + 1) % SZ(B)], B[eB])));

    eA = (eA + 1) % SZ(A);

}

return ans;

}


完整源码（含几何模板、读入、Solve 框架）：

<details>
<summary>展开完整 C++ 源码（Bridge_Across_Islands.cpp）</summary>

完整源码 ~840 行较长，含整套几何模板（`Point` / `Line` / `cross` / `distanceSS` / `reorder_polygon` 等）+ `cal_min_dis_two_convex` + 多组数据 main。直接下载页面末尾附件 `Bridge_Across_Islands.cpp.txt`（去掉 `.txt` 后缀即为 `.cpp`）。

</details>

# 心路历程（TLE → WA → AC）

1. **第一版 TLE**：用「`dis2 < dis1` 顶点-边距离贪心」推进 —— 在 $A$ 朝 $B$ 那半弧上确实单调，但当 $i$ 越过 $A$ 的背面弧后单调性破裂， $j$ 想往回走但只能 forward，**陷在 $B$ 上转圈**，OJ 测出 TLE。
2. **第二版 WA**：换成 `cross(a, b')` 角度判定，单次 `cal_min_dis_two_convex(A, B)` 调用 —— 本地 cyaron stress 用近圆形测 5000 case 全过、提交 OJ WA。`cyaron-stress` skill 警告过：**cyaron `Polygon.convex_hull` 默认近圆形是对拍盲区**，必须主动用 ellipse / spiked / heart / lemon 等曲率非均匀形状才能触发反例。换成椭圆 + spike 形状后，stress seed 24 立刻给出 `yMnA + yMxB` 配对失效的反例（见附件 `counterexample_seed24.html`）。
3. **第三版 AC**：加上 `(B, A)` 反向调用取 $\min$ 补对偶。

\textcolor{red}{**收获心法**}：

- 旋转卡壳推进准则用 **`cross` 角度差** 而不是 **dis 单峰**。「dis 单峰」是教材级 fact 但只在曲率均匀分布下成立。
- 单次调用对偶不完整 —— 看 mentor.tex 里 me/mentor 第 3 步对话录有详细推导，需要 `(A, B)` + `(B, A)` 反向。
- 对拍**必须**用非均匀曲率形状（椭圆 / spike / heart / lemon）破盲区；cyaron `Polygon.convex_hull` 默认值就是盲区本身。

# 附件

Bridge_Across_Islands_html_demos.zip

mentor.tex 编译产物 PDF —— me/mentor 5 步推导对话录（题面 / 三类特征对 / facing 弧 / 旋转卡壳骨架 / cross 推进准则）

Bridge_Across_Islands.cpp.txt

CF Round 1093 Div2 D2 - Unique Values (Hard version)

Posted on 2026-05-09 Edited on 2026-05-11

题目大意

原题：CF Round 1093 Div2 D2 - Unique Values (Hard version)（rating 1900）

交互题。有一个长度 $2n+1$ 的隐藏数组 $a$ ，元素值在 $[1, n]$ 之间；其中有且仅有一个值出现 3 次，其余每个值都恰好出现 2 次。要求找出那个出现 3 次的值的三个下标。

每次询问可以选一个下标子集 $S$ ，judge 会返回 $\{a_i : i \in S\}$ 这个多重集里恰好出现一次的值的个数（即把一对一对的去掉以后还剩几种）。

Easy version: $\le 50$ 次询问。Hard version（本题）： $\le 33$ 次询问。 $n \le 1000$ 。

思路讲解

一句话

设那个特殊值（出现 3 次的）为 $T$ ，三个位置 $p_1 < p_2 < p_3$ 。33 次预算 = 3 段二分 × 11 次——每段用 bit-trick 在长度 $\le 2n+1 \le 2001$ 的范围里锁一个位置， $\lceil \log_2 2001 \rceil = 11$ 。三段分别独立设计一个关于 $k$ 单调的奇偶谓词，bit-trick 收敛。

核心 trick：贡献奇偶表

对任一询问集合 $S$ ，记 $\text{len} = |S|$ ， $\text{res}$ 为 judge 返回值。每个值 $v$ 对 $\text{len} - \text{res}$ 的贡献只取决于它在 $S$ 中的 count：

count	贡献 = count − [count==1]	奇偶
0	0	偶
1	0	偶
2	2	偶
3	3	奇

关键不变量：只有 count = 3 那档贡献奇数。本题里能让某个值 count = 3 的，只有那个出现 3 次的特殊值 $T$ 。所以 $(\text{len} - \text{res}) \bmod 2 = 1 \iff T \text{ 在 } S \text{ 里凑齐 } 3 \text{ 个 position}$ 。

其他值（出现 2 次的 double）count $\le 2$ ，贡献全偶，自动从奇偶位上消失——这就是奇偶谓词的威力，doubles 不来添乱。

第 1 段：找 $p_3$

询问 $S_k = [1..k]$ 。 $T$ 在 $S_k$ 里 count = 3 当且仅当 $k \ge p_3$ （三个位置全进来）。

$(k - \text{res}) \bmod 2 = 0 \iff k < p_3$

谓词在 $[0, p_3 - 1]$ 真， $[p_3, N]$ 假。bit-trick 从 $k = 0$ 起按 $2^i$ 加位，找最大的真 $k$ = $p_3 - 1$ ，加 1 即 $p_3$ 。

ll pos3 = 0;
for (int i = __lg(N); i >= 0; --i) {
    ll k = pos3 + (1ll << i);
    if (k > N) continue;
    ll res = query(1, k);
    if ((k - res) % 2 == 0) pos3 = k;
}
pos3++;

第 2 段：找 $p_1$

知道 $p_3$ 后，询问 $S_k = [k..p_3]$ （后缀）。 $T$ 在 $S_k$ 里 count = 3 当且仅当 $k \le p_1$ （三个位置都在 $[k..p_3]$ 里）。

$(\text{len} - \text{res}) \bmod 2 = 0 \iff k > p_1$

谓词在 $[p_1+1, p_3]$ 真， $[1, p_1]$ 假。bit-trick 从 $k = p_3$ 起降序减位，找最小的真 $k$ = $p_1 + 1$ ，减 1 即 $p_1$ 。

ll pos1 = pos3;
for (int i = __lg(pos3); i >= 0; --i) {
    ll k = pos1 - (1ll << i);   // ← 用当前 pos1，不是 pos3
    if (k < 1) continue;
    ll res = query(k, pos3);
    ll len = pos3 - k + 1;
    if ((len - res) % 2 == 0) pos1 = k;
}
pos1--;

第 3 段：找 $p_2$ （最绕的一段）

$p_1, p_3$ 已知，找 $p_2 \in (p_1, p_3)$ 。这一段最容易写错——不要用「query $[1..k] \setminus \{p_1, p_3\}$ 看 res 是否为 0」这种谓词，那个不单调。

正确设计：让 $T$ 在询问集合里的 count 在 $k$ 跨过 $p_2$ 时从 2 跳到 3（正好覆盖贡献表里的奇偶分界点）。

$S_k = \{p_3\} \cup [p_1..k], \quad k \in [p_1, p_3 - 1]$

T 在 $S_k$ 里： $p_1$ 必入（在 $[p_1..k]$ 里）， $p_3$ 必入（显式塞）， $p_2$ 当且仅当 $k \ge p_2$ 时入。

$k$ vs $p_2$	$T$ count	$(\text{len}-\text{res}) \bmod 2$
$k < p_2$	2	0（偶）
$k \ge p_2$	3	1（奇）

谓词 $\iff k < p_2$ ，bit-trick 从 $k = p_1$ 起加位，找最大真 $k$ = $p_2 - 1$ ，加 1 即 $p_2$ 。

ll pos2 = pos1;
for (int i = __lg(pos3 - pos1); i >= 0; --i) {
    ll to = pos2 + (1ll << i);
    if (to >= pos3) continue;
    auto [len, res] = query(pos1, to, pos1, pos3);   // [pos1..to] ∪ {pos1, pos3}
    if ((len - res) % 2 == 0) pos2 = to;
}
pos2++;

询问数核账

段	范围	bit 数上界
$p_3$	$[1, 2n+1]$	$\lceil \log_2 (2n+1) \rceil \le 11$
$p_1$	$[1, p_3]$	$\lceil \log_2 p_3 \rceil \le 11$
$p_2$	$[p_1, p_3 - 1]$	$\lceil \log_2 (p_3 - p_1) \rceil \le 11$

合计 $\le 33$ ，正好卡到题目限制。Easy version 给 50 次相对宽松，Hard 这 33 次每段都不能浪费一次询问——所以三个 bit-trick 必须用 continue 越界保护省下不必要的查询。

AC 代码

AC 提交链接

展开完整 C++ 源码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define SZ(a) ((long long) a.size())

using namespace std;
using ll = long long;

ll lT, testcase;

ll query(const vector<ll> &posLs) {
    cout << "? " << SZ(posLs) << " ";
    for (auto p: posLs) cout << p << " ";
    cout << endl;
    ll res;
    cin >> res;
    return res;
}

ll query(ll l, ll r) {
    vector<ll> posLs;
    for (int i = l; i <= r; ++i) posLs.push_back(i);
    return query(posLs);
}

pair<ll, ll> query(ll l, ll r, ll pos1, ll pos3) {
    vector<ll> posLs;
    set<ll> st = {pos1, pos3};
    for (int i = l; i <= r; ++i) st.insert(i);
    posLs.reserve(SZ(st));
    for (auto p: st) posLs.push_back(p);
    return {SZ(posLs), query(posLs)};
}

void Solve() {
    ll N;
    cin >> N;
    N = 2 * N + 1;

    // 第 1 段: 找 p3
    ll pos3 = 0;
    for (int i = __lg(N); i >= 0; --i) {
        ll k = pos3 + (1ll << i);
        if (k > N) continue;
        ll res = query(1, k);
        if ((k - res) % 2 == 0) pos3 = k;
    }
    pos3++;

    // 第 2 段: 找 p1
    ll pos1 = pos3;
    for (int i = __lg(pos3); i >= 0; --i) {
        ll k = pos1 - (1ll << i);
        if (k < 1) continue;
        ll res = query(k, pos3);
        ll len = pos3 - k + 1;
        if ((len - res) % 2 == 0) pos1 = k;
    }
    pos1--;

    // 第 3 段: 找 p2 (强制塞 {p1, p3} 当 baseline)
    ll pos2 = pos1;
    for (int i = __lg(pos3 - pos1); i >= 0; --i) {
        ll to = pos2 + (1ll << i);
        if (to >= pos3) continue;
        auto [len, res] = query(pos1, to, pos1, pos3);
        if ((len - res) % 2 == 0) pos2 = to;
    }
    pos2++;

    cout << "! " << pos1 << " " << pos2 << " " << pos3 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase) Solve();
    return 0;
}

心路历程（WA → MLE → AC，被 D2 教做人的 4 个小时）

这道题头一次过 D1（Easy 50 次询问）那版还挺顺，三段二分各用 17 次差不多卡进去就完了。到 D2 把预算压到 33 次才开始遭罪——核心不是"次数压紧"这件事，而是 $p_2$ 那段我第一版完全写歪了思路，后面几次提交几乎都是在为最初这个错误的设计买单。

❌ 第一版：用 `!res` 当谓词，谓词根本不单调

第一版的想法是「query $[1..k] \setminus \{p_1, p_3\}$ ，看 res 是不是 0」。直觉是「subset 里所有值都成对了 = res = 0 = 还没碰到 $p_2$ 」，然后 bit-trick 找最大的 res = 0 的 $k$ 。

第一次提交：WA on test 1。看了一会才发现一个特别傻的低级错误：

1 2	plus(pos2, 1); // 这行返回值被丢了！ cout << "! " << pos1 << " " << pos2 << " " << pos3 << endl;

plus 是个按值收 pos2 的纯函数返回新值，我没赋值回来。pos2 全程是 0，输出 ! 1 0 3 直接非法。改成 pos2 = plus(pos2, 1)。

❌ 修了 line 179 后才发现：`!res` 这个谓词本身就不单调

修完那个赋值，跑反例 $a = [1, 2, 3, 2, 1, 3, 1]$ （ $T=1$ ， $p_2 = 5$ ）发现：

$k$	subset 值	res
0	$\varnothing$	0
2	$\{2\}$	1
3	$\{2, 3\}$	2
4	$\{2, 3, 1\}$	3
5	$\{2, 3, 1, 1\}$	2
6	$\{2, 3, 1, 1, 2\}$	1

res = 0 只在 $k = 0$ 出现一次，bit-trick 完全收敛不到 $p_2 - 1$ 。res = 0 要求 (a) $p_2 > k$ 且 (b) 所有 doubles 在 $[1..k]$ 里都凑成对——条件 (b) 完全取决于数组排列，不单调，bit-trick 没救。

✅ 重新设计：让 $T$ 的 count 落在贡献奇偶分界点 $2 \to 3$

被这个反例打醒以后回去想，关键是奇偶性技巧。每个值对 $\text{len} - \text{res}$ 的贡献只看 count，count = 3 那档唯一贡献奇数。所以谓词应该让 $T$ 的 count 在 $k$ 跨过 $p_2$ 时正好从偶（=2）跳到奇（=3）。

解法：强制把 $p_1$ 和 $p_3$ 塞进询问当 baseline，让 $T$ count 起步 = 2；可变前缀 $[p_1+1..k]$ 决定 $p_2$ 进不进来。doubles 全偶贡献，自动失声。

这一刻才意识到为什么 Easy 给 50 次而 Hard 卡 33 次——Hard 是逼你想出贡献奇偶表那张图，否则你写一段「 $\text{res} == 0$ 」走 32 次询问的解法在 Easy 能水过去（其实也水不过去因为不收敛），但 Hard 必须靠奇偶性拿满 11 + 11 + 11。

❌ 第二版：query 函数签名想得不干净

写了个 query(pos1, to, pos1, pos3) 4-arg 重载，意思是 [pos1..to] ∪ {pos1, pos3}。Claude 提醒 pos1 重复传了（既是区间端点又是 extra），但实测因为内部用 set<ll> 去重，功能上没坏。算是一个"看起来丑但实际能跑"的设计——code review 视角不优雅，但提交跑下来对的，就先不动它了。

❌ 第三版：`to` 没卡上界 → MLE on test 2

写完 $p_2$ 那段提交：MLE on test 2，262100 KB / 256 MB。看了一会想不通：算法里 vector<ll> 都是局部变量，每次 query 完就析构，per-query 内存几 KB，单次 Solve $\le$ 100 KB，怎么会到 256 MB？

最后定位到 line 173 没卡 to < pos3：

for (int i = __lg(pos3 - pos1); i >= 0; --i) {
    ll to = pos2 + (1ll << i);
    // 没有越界保护！
    auto [len, res] = query(pos1, to, pos1, pos3);
    ...
}

bit-trick 推进时，trial 值 to 可以超过 pos3 甚至 N = 2n+1——比如 $p_3 \approx 2000$ , $p_{2,\text{actual}} \approx 1500$ , $p_1 = 1$ 这种局，几次 take 之后 pos2 ~ 1985，下一轮 $i=5$ 算出 to = 2017 > N，把 $2002, ..., 2017$ 这种不存在的位置全发给 judge。Judge 返 -1，但代码不退出继续读流，stream 关掉以后所有 cin 都 fail（C++11+ 落 res = 0），predicate 退化成"按 k 奇偶决定 take"，状态彻底污染。

Per problem statement: After receiving such a response, your program should immediately terminate.

我没退出，导致后面跑成什么样都不可控——MLE 大概率是 stdout pipe 被 judge 关掉以后 iostream 缓冲区累积，或者多 test cases 在烂状态下连续跑出来的 cascade。根因是单次 invalid query 没立刻退出。

修法：

1 2	ll to = pos2 + (1ll << i); if (to >= pos3) continue; // ← 补这一行

顺手把 $p_3$ 段 if (k > N) continue; 和 $p_1$ 段 if (k < 1) continue; 也补了——这俩同样能越界，只是没造成 MLE。

❌ 第四版：`p_1` 段 bit-trick 写错变量

补完三处 continue 还过不了。再仔细看 $p_1$ 段：

for (int i = __lg(pos3); i >= 0; --i) {
    ll k = pos3 - (1ll << i);   // ← 用了 pos3 不是 pos1!
    ...
    if (...) pos1 = k;
}

bit-trick 降序的标准套路是每轮用当前的 pos1****（已经被前几轮压低过）减 $2^i$ 当 trial 值，让 pos1 单调下降收敛到 $p_{1,\text{actual}} + 1$ 。我写成 pos3 - (1ll << i)， $p_3$ 整个循环不变，每轮 trial 都是固定的 $p_3 - 2^i$ 那 11 个偏移量——根本不是 bit-trick，最后 pos1 等于最后一次 predicate 真的那个 $k$ ，几乎一定是 $p_3 - 1$ （除非 $p_{1,\text{actual}} = p_3 - 1$ ）。

为什么 sample 蒙过了：sample 是 $p_1 = 1, p_3 = 3$ ，循环只 2 轮，恰好 $i=0$ 时 $k = p_3 - 1 = 2$ 就是 $p_{1,\text{actual}} + 1$ ，pos1 = 2，pos1-- = 1。完美对的——但完全是巧合。

改成 ll k = pos1 - (1ll << i);，提交：AC。提交号 374001488。

总结一下踩过的坑

lambda 返回值丢了——低级 typo 但确实写过，下次 IDE warning 多看一眼
!res 不单调——奇偶谓词 vs 等于零谓词的认知差。等于零是偶发性的、依赖排列；奇偶性才是结构性的，doubles 自动失声
bit-trick trial 值没卡上界——3 个段都要保护：k > N / k < 1 / to >= p_3。MLE 不是因为单次内存，是因为没有遵守 read -1 → exit 的协议，状态污染后续的 cascade 才把内存搞炸的
bit-trick 用了静态变量代替累积变量——pos3 - 2^i vs pos1 - 2^i，sample 巧合下还能过，靠肉眼看完全看不出来，必须自己手算几个反例
Easy → Hard 不是单纯次数压紧——往往 Hard 在逼你换更结构化的 idea。这道题 Hard 的 33 次是直接告诉你"每段必须 $\lceil \log_2 N \rceil$ 不能浪费"，反推奇偶谓词的设计

附件

📄 p2 奇偶谓词的设计思路（独立讲解 PDF，含贡献奇偶表 + 反例数组完整 trace）

D2_Unique_Values_Hard_version.cpp.txt

📄 p2 奇偶谓词的设计思路（独立讲解 PDF，含贡献奇偶表 + 反例数组完整 trace）

D2_Unique_Values_Hard_version.cpp.txt

HDU 2026 春季联赛 7 1001 - Card（裴蜀定理）

Posted on 2026-05-08 Edited on 2026-05-09

杭电 2026 春季联赛 7 第 1 题（HDU 1001）。原题：https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001

题目大意

无向连通图 $n$ 点 $m$ 边，每条边有正权 $w$ 表示走这条边耗费的时间。每个点 $i$ 上有一瓶魔力药水 $a_i$ ，喝一瓶可以让魔力值 $\pm a_i$ （任意次、不耗时间）。从 $1$ 号点出发、初始魔力 $0$ ，目标让魔力值恰好等于 $V$ ，求最少总移动时间；不可达输出 -1 。

约束 $1 \le n, m \le 10^4$ ， $1 \le V, a_i, w \le 10^9$ 。题面保证 $a_1$ 的所有质因数都在 $V$ 的质因数集合中（注意这不蕴含 $a_1 \mid V$ ）。

样例

输出 0 。 $V = 18 = 9 \cdot a_1$ ，起点直接喝 9 次正向药水就行，不用动。

思路讲解

一句话

走过的点的 $a_i$ 通过裴蜀定理可以拼出 $\gcd$ 的所有倍数；问题等价于找一条从 $1$ 出发的路径，让经过点的 $\gcd$ 整除 $V$ ，最小化总边权。 $\gcd$ 状态只有 $O(\log V)$ 种，分层图 Dijkstra 直接跑。

裴蜀定理转化

走过点集 $S$ 时，每个点 $i \in S$ 都可以喝若干次正向 / 反向药水。最终魔力值是

$\sum_{i \in S} k_i \cdot a_i, \quad k_i \in \mathbb{Z}.$

也就是关于 $\{a_i\}_{i \in S}$ 的整数线性组合。

🧮 Note: 裴蜀定理（Bézout）： $\{a_i\}$ 的整数线性组合恰好覆盖 $\gcd(a_i : i \in S)$ 的全部整数倍。

所以走过点集 $S$ 的可达魔力值集合 $=$ $\gcd(a_i : i \in S)$ 的全体整数倍。目标 $V$ 可达等价于 $\gcd(S) \mid V$ 。

殊途同归一句：经过一个点不强制喝它的药水，但跳过 $=$ 把它从计入 gcd 的集合里去掉，gcd 只会变大、整除关系只会更难满足。所以最优策略就是把走过的点全喝，状态干脆只追"目前路径上点的 gcd"一个量。

gcd 的状态数 $=$ $O(\log V)$

起点 gcd $= a_1$
每加入一个新点 $v$ ， gcd 变成 $\gcd(g, a_v)$ ：要么不变（ $a_v$ 是 $g$ 的倍数），要么至少缩小一半（变成 $g$ 的真因子）

从 $a_1$ 一路降到 $1$ 最多 $\log_2 a_1 = O(\log V)$ 步。出现过的 gcd 全是 $a_1$ 的因数，每个节点最多 $O(\log V)$ 种 gcd 状态。

关键不变量：状态空间上界 $n \cdot O(\log V) \approx 10^4 \cdot 30 = 3 \times 10^5$ ，分层图 Dijkstra 完全跑得动。

分层图 Dijkstra

状态 $(u, g)$ ：当前在节点 $u$ 、当前路径上点的 gcd 是 $g$ 。

转移：从 $(u, g)$ 沿边 $(u, v, w)$ 到 $(v, \gcd(g, a_v))$ ， dist 加 $w$ 。

起点 $(1, a_1)$ ， dist $= 0$ 。

答案：扫所有可达状态 $(u, g)$ ，其中满足 $V \bmod g = 0$ 的最小 dist 即为答案。

边权全正、状态空间有限，标准 Dijkstra（pq + lazy stale check）就够。

实现要点

用 vector<map<ll, ll>> mp(n+2) 存每个节点的 gcd → dist
pq pop 出来必须先判 step > mp[u][gcd] 跳过 stale 态——否则同一个状态反复被 push 出来展开邻居，状态量爆炸 TLE
起点先特判 V % a_1 == 0 直接输出 0
找到 ans 后加剪枝 step + w >= ans continue
ans 永远是 LLONG_MAX 时输出 -1 ——题面保证 $a_1$ 的质因数 $\subseteq V$ 的质因数，但不蕴含 $a_1 \mid V$ ，反例 $a_1 = 4, V = 18$ 下若所有 $a_i \in \{4, 8, 12, \dots\}$ 永远凑不出 $18$ ，必须返回 -1

AC 代码

AC 提交链接

展开完整 C++ 源码

// teamname: Gospel_rock
/**
 * Problem: Card
 * Contest: 2026 杭电春季联赛 7
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001
 * Created: 2026-05-08 22:53:45
 * Author: Gospel_rock
 */

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

struct UStepGcd {
    ll u, gcd, step;
    bool operator<(const UStepGcd &o) const { return step > o.step; }
};

void Solve() {
    ll N, M, V;
    cin >> N >> M >> V;
    vector<ll> A(N + 2);
    vector<vector<array<ll, 2>>> g(N + 2);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= M; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    if (V % A[1] == 0) { cout << 0 << "\n"; return; }
    priority_queue<UStepGcd> pq;
    pq.push({1, A[1], 0});
    vector<map<ll, ll>> mp(N + 2);
    ll ans = LLONG_MAX;
    while (!pq.empty()) {
        auto [u, gcd, step] = pq.top();
        pq.pop();
        if (step > mp[u][gcd]) continue;
        for (auto [v, w] : g[u]) {
            ll to_gcd = __gcd(A[v], gcd);
            if (V % to_gcd == 0) ans = min(ans, step + w);
            if (step + w >= ans) continue;
            if (!mp[v].contains(to_gcd) || step + w < mp[v][to_gcd]) {
                mp[v][to_gcd] = step + w;
            } else {
                continue;
            }
            pq.push({v, to_gcd, step + w});
        }
    }
    if (ans == LLONG_MAX) { cout << -1 << "\n"; return; }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) Solve();
    return 0;
}

心路历程（TLE → WA → AC）

第一版 TLE

priority_queue + map<ll, map<ll, ll>> 直接交，TLE 。原因：

pop 出来没做 stale check ，直接处理邻居 → 同一个 (u, g) 状态被反复 push、pop、展开邻居，pq 状态量指数膨胀
map<ll, map<ll, ll>> 嵌套红黑树，每次 contains / operator[] 都是 O(log²) ，常数惨

修法：

pop 之后立刻 if (step > mp[u][gcd]) continue;
外层换成 vector<map<ll, ll>> （节点下标天然是 vector 索引）
顺手加 step + w >= ans 早剪枝

第二版 WA

修完 TLE 跑通样例，交上去 WA 。原因：

ll ans = LLONG_MAX ，不可达时没转 -1 直接打印了 9223372036854775807
题面要求不可达输出 -1

修法：

1	cout << (ans == LLONG_MAX ? -1 : ans) << "\n";

题面"保证 $a_1$ 的质因数 $\subseteq V$ 的质因数"乍看像在保证可达，其实不蕴含 $a_1 \mid V$ ：例如 $a_1 = 4, V = 18$ ， $\{2\} \subseteq \{2, 3\}$ 满足前提，但 $4 \nmid 18$ 。如果整张图所有 $a_i$ 都是 $4$ 的倍数（gcd 永远是 $4$ 的倍数）就永远凑不出 $18$ ，必须返回 -1 。

加上这一行后 AC 。

附件

（暂无）

CCPC 2023 Guangdong M - Computational Geometry（不是旋转卡壳）

Posted on 2026-05-07 Edited on 2026-05-09

题目大意

CCPC 2023 Guangdong Provincial M - Computational Geometry（CF Gym 104369 镜像）。

给定逆时针顺序凸 $N$ 边形顶点 $A_0, A_1, \ldots, A_{N-1}$ ，选两个不相邻的顶点 $A_{i_1}, A_{j_1}$ 把多边形切成两段 sub-polygon $Q$ 和 $R$ ，最小化

\mathrm{diam}(Q)^2 + \mathrm{diam}(R)^2

数据范围 $N \le 5000$ ，多组数据。

样例

$N = 4$ ， $\{(1,0), (2,0), (1,1), (0,0)\}$ ，期望 $\mathbf{4}$ ：切 $(0, 2)$ 把菱形切成两个三角形，每半 $d^2 = 2$ 。
$N = 6$ ，spike-3 hull，期望 $\mathbf{44}$ ：切 $(2, 4)$ ， $Q$ 直径 $^2 = 10$ 、 $R$ 直径 $^2 = 34$ 。

思路讲解

普通 RC 求凸多边形直径为什么对

直观理解：拿一把卡尺（两条平行 supporting line）夹住凸多边形旋转一圈，最大间距就是直径。算法上对应「外循环 r 跑遍每条边、内层 l 跟随推进」——每条边都被卡过一遍，所以直径必出现在某次「边-反极顶点」的 candidate 里，必被 collect。

本题改造为什么有问题——边覆盖不全

子弧 + 闭合 chord 是一个闭子多边形 $R'$ ，对它跑经典 RC 是对的——但前提是把 $R'$ 的所有边都卡过。

我的改造里 edge 从 $i$ 起步靠 need_edge_move 单调向前推进，永远停留在原多边形的相邻顶点对 $(A_e, A_{e+1})$ 上。但 $R'$ 的边集 = 子弧上的原边 + 一条非相邻的 chord $(A_j, A_i)$ ——chord 是非相邻顶点对，edge 数值永远不会取到它。

卡尺没把 $R'$ 的所有边卡过一遍，自然漏直径。

区间 DP 正解

状态

$\mathrm{dp}[i][j]$ = 以子弧 $A_i \to A_{i+1} \to \cdots \to A_j$ （CCW 沿原多边形顺序，含两端）为顶点集的闭子多边形的直径² ——即该顶点集上所有点对的 $\|A_p - A_q\|^2$ 最大值。

递推

\mathrm{dp}[i][j] = \max\big(\,\mathrm{dp}[i{+}1][j],\ \mathrm{dp}[i][j{-}1],\ \|A_i - A_j\|^2\,\big)

正确性：把顶点集 $\{i, i{+}1, \ldots, j\}$ 上所有无序点对 $(p, q)$ 按是否含两端点 $i, j$ 分三类：

不含 $i$ ：点对 $\subseteq \{i{+}1, \ldots, j\}$ ，覆盖在 $\mathrm{dp}[i{+}1][j]$
不含 $j$ ：点对 $\subseteq \{i, \ldots, j{-}1\}$ ，覆盖在 $\mathrm{dp}[i][j{-}1]$
两端都含：唯一点对 $(i, j)$ ，单独的 $\|A_i - A_j\|^2$ 项

三类不重不漏、取 max 即全集直径²。

为什么 DP 走得通、RC 走不通

关键对比：这个递推式完全不依赖凸性——它就是个「枚举所有点对取 max」的 $O(N^2)$ 朴素 DP。「凸」在 RC 路线里是刚需（卡尺单峰让对蹵点单调推进 → $O(N)$ ）；DP 路线不贪「凸」这点便宜、只用上「顶点集是连续子弧」这个事实。一句话：RC 吃结构红利换 $O(N)$ ，DP 不吃红利 $O(N^2)$ 但保命。

循环顺序是硬约束

跟一般区间 DP 一样：len 在外、 $i$ 在内。奇心把 $i$ 写在外会踩心路历程 7 那个坑（ $2N$ pass 兜底也救不回）。

切法枚举

枚举不相邻顶点对 $(i_1, j_1)$ 作为 chord：

\mathrm{ans} = \min_{j_1 \ge i_1 + 2,\ j_1 \not\equiv i_1 \pm 1 \pmod N} \big(\,\mathrm{dp}[i_1][j_1] + \mathrm{dp}[j_1][i_1]\,\big)

两项分别是切后两段子弧的直径²——dp 表索引是循环的， $\mathrm{dp}[j_1][i_1]$ 自动覆盖另一段。cross 检查 $\ne 0$ 顺手筛掉两类退化： wrap-adjacent切（如 $(0, N-1)$ 在循环视角下其实是相邻点），与共线退化切（chord 踩在原多边形某条边上）。

复杂度

填 dp 表 $O(N^2)$ 个状态 × $O(1)$ 转移、枚举切法 $O(N^2)$ 、总 $O(N^2)$ 。 $N \le 5000$ 下填表 $2.5 \times 10^7$ 次贴近 TL，多组数据下实测 3312 ms / 6s 限制。

AC 代码

AC 提交：codeforces.com/gym/104369/submission/373844988

切到 $O(N^2)$ 区间 DP 后 AC（3312 ms / 192600 KB， $N \le 5000$ 多组数据贴近 TL）。

展开 Solve() 与 distancePPNorm 的核心实现

// dp[i][j] = 子弧 A_i → A_j（CCW，含两端）的凸子多边形直径²
// 递推：dp[i][j] = max(dp[i+1][j], dp[i][j-1], ‖A_i - A_j‖²)
// 关键：len 外、i 内 —— len 大的依赖 len 小的，i 在外的话同 len 不同起点的
//       dp[i+1][·] 还没填过，单遍跑不出来；2N pass 兜底也是错觉

auto distancePPNorm(const Point &a, const Point &b) {
    return (a - b).norm();  // 返回平方距离，不开根
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<vector<ull>> dp(N, vector<ull>(N));
    for (int len = 1; len < N; ++len) {
        for (int i = 0; i < N; ++i) {
            int ip1 = (i + 1) % N;
            int j = (i + len) % N;
            int j_1 = (i + len - 1) % N;
            if (len == 1) { dp[i][j] = distancePPNorm(A[i], A[j]); continue; }
            dp[i][j] = max({dp[ip1][j], dp[i][j_1], (ull) distancePPNorm(A[i], A[j])});
        }
    }
    // 枚举切法 (i1, j1)，分多边形为子弧 [i1..j1] 与 [j1..i1+N]
    ull ans = ~0ULL;  // ⚠️ 不能用 INF=(1ll<<61)-1，被 1.6e19 候选反超 → WA on test 7
    for (int i1 = 0; i1 < N; ++i1) {
        int j2 = i1;
        for (int j1 = i1 + 2; j1 < N; ++j1) {
            int i2 = j1;
            // cross != 0 顺手筛掉 wrap-adjacent (0, N-1) 与共线退化切
            if (cross(A[i1], A[(i1+1)%N], A[j1]) != 0
             && cross(A[i2], A[(i2+1)%N], A[j2]) != 0) {
                ans = min(ans, dp[i1][j1] + dp[i2][j2]);
            }
        }
    }
    cout << ans << "\n";
}

心路历程

直觉把「凸多边形直径 → 旋转卡壳」和「切法枚举」硬嫁接，写出 vanilla RC + 子弧增长版
sample 1 ( $n=4$ ) 期望 $4$ 实测 $3$ ，开始 debug
第一发现： $\mathrm{dp}[2][0] = 1$ 漏了 $(A_2, A_3)$ 这对距离——up 起步 $i+2$ ，arc 起点附近的 pair 永远不进 candidate
第二发现：dp[edge][up] = ans 索引用动态 edge 而非外层切起点 $i_\mathrm{outer}$ ，dp 矩阵大量被错位写入（附带 bug）
spike-3 对拍反例（差 $7.45\%$ ）让「算法是结构性错的、不是 off-by-one」心服口服
抓到根因：RC 之所以对，因为它每条边都卡过 + 每个顶点都反极过；改造版两条都破了
DP 重写又踩循环顺序坑——RC 死了之后转 $O(N^2)$ 区间 DP（ $\mathrm{dp}[i][j]$ = 子弧 $A_i \to A_j$ 凸子多边形直径² ），递推 $\mathrm{dp}[i][j] = \max(\mathrm{dp}[i+1][j],\ \mathrm{dp}[i][j-1],\ \|A_i - A_j\|^2)$ 。第一发先把 $i$ 写在外、 $\mathrm{len}$ 写在内，再跑 $2N$ 遍当兜底——错：

当前算 $\mathrm{dp}[i][j]$ 需要 $\mathrm{dp}[i+1][j]$ （len $-1$ 但起点变了）。 $i$ 外 len 内的顺序下，处理 $i=0$ 时 $\mathrm{dp}[1][\cdot]$ 整行都还是 $0$ ，根本没轮到 $i=1$ 那层
$2N$ pass 兜底也救不回来：pass 1 全程用 $0$ 推导出脏值；pass 2 处理 $i=0,\ \mathrm{len}=3$ 时要 $\mathrm{dp}[1][3]$ ，可这个值是 pass 1 用 $\mathrm{dp}[2][3]=0$ 算出来的脏值——pass 2 来不及修
正确写法：len 外、 $i$ 内，一遍即可

心法：「len 小的之前都被计算了」这个直觉成立的前提是 len 在外。 $i$ 在外的话，给定 $i$ 你确实按 len 升序填了 $\mathrm{dp}[i][\cdot]$ ，但同 len 不同起点的 $\mathrm{dp}[i+1][\cdot]$ 还压根没碰过——「 $2N$ pass 兜底」是错觉：每跑一遍正确性最多渗透一层 len，最坏要 $N$ 遍且仍受脏值污染。

附件

详细 debug 记录与图示见下方嵌入 PDF —— rc_breakdown.pdf ，5 页，含凸多边形 + 反极顶点单峰示意 / 闭子多边形 $R'$ / forbidden up + chord $\times$ 标记 / $\mathrm{dp}[3][1]$ trace 表。

rc_breakdown.pdf — 5 页 debug 记录：经典 RC 为什么对（凸多边形 + 反极顶点 + 距离单峰）/ 闭子多边形 R’ / forbidden up + chord ✗ 标记 / dp[3][1] trace 表

题目大意

数据范围

思路讲解

一句话

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

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

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

第 4 步：完整算法

📎 动画与源码

AC 代码

心路历程

附件

题目大意

输入

输出

样例

思路讲解

一句话

把最近距离归并到「顶点 → 线段」

facing 弧 + 单调推进

初始 facing pair：A 最低 + B 最高

cross(a, b') 推进准则（核心）

为什么必须 (A, B) + (B, A) 各调一次

题目大意

思路讲解

一句话

核心 trick：贡献奇偶表

第 1 段：找 p3p_3p3​

第 2 段：找 p1p_1p1​

第 3 段：找 p2p_2p2​ （最绕的一段）

询问数核账

AC 代码

心路历程（WA → MLE → AC，被 D2 教做人的 4 个小时）

❌ 第一版：用 !res 当谓词，谓词根本不单调

❌ 修了 line 179 后才发现：!res 这个谓词本身就不单调

✅ 重新设计：让 TTT 的 count 落在贡献奇偶分界点 2→32 \to 32→3

❌ 第二版：query 函数签名想得不干净

❌ 第三版：to 没卡上界 → MLE on test 2

❌ 第四版：p_1 段 bit-trick 写错变量

总结一下踩过的坑

附件

题目大意

样例

思路讲解

一句话

裴蜀定理转化

gcd 的状态数 === O(log⁡V)O(\log V)O(logV)

分层图 Dijkstra

实现要点

AC 代码

心路历程（TLE → WA → AC）

第一版 TLE

第二版 WA

附件

题目大意

样例

思路讲解

普通 RC 求凸多边形直径为什么对

本题改造为什么有问题——边覆盖不全

区间 DP 正解

状态

递推

为什么 DP 走得通、RC 走不通

循环顺序是硬约束

切法枚举

复杂度

AC 代码

心路历程

附件

`cross(a, b')` 推进准则（核心）

为什么必须 `(A, B)` + `(B, A)` 各调一次

第 1 段：找 $p_3$

第 2 段：找 $p_1$

第 3 段：找 $p_2$ （最绕的一段）

❌ 第一版：用 `!res` 当谓词，谓词根本不单调

❌ 修了 line 179 后才发现：`!res` 这个谓词本身就不单调

✅ 重新设计：让 $T$ 的 count 落在贡献奇偶分界点 $2 \to 3$

❌ 第三版：`to` 没卡上界 → MLE on test 2

❌ 第四版：`p_1` 段 bit-trick 写错变量

gcd 的状态数 $=$ $O(\log V)$