洛谷 P5939 - 折线

Posted on 2026-05-19

题目大意

洛谷 P5939 [POI 1998 R3] 折线

平面上给 $n$ 个格点。一条 平直折线 从左到右一笔画过去，每一段和 $x$ 轴的夹角都在 $[-45^\circ, 45^\circ]$ 之间。问：最少画多少条平直折线，才能盖住所有点？

数据范围

$1 \le n \le 30000$ ， $0 \le x_i, y_i \le 30000$ 。时限按常规 1s 算，目标复杂度 $O(n\log n)$ 。

样例

样例 1：5 个点 (2,3) (3,4) (4,5) (1,6) (12,27) ，答案 3 。样例 2：6 个点，答案 3 。

思路讲解

一句话

夹角 $\le 45^\circ$ 等价于斜率绝对值 $\le 1$ ，也就是 $|\Delta y| \le \Delta x$ 。把坐标系转 $45^\circ$ ，令 $u = x+y$ 、 $v = x-y$ ，"两点能串在同一条折线上"就变成 $(u,v)$ 两维都不减 的支配关系；于是一条折线 = 一条链，最少折线数 = 最小链覆盖 ；由 Dilworth（导弹拦截那一套），它等于 $v$ 序列的 最长严格下降子序列 长度， $O(n\log n)$ 。

第一步：把角度约束代数化

设两个格点 $P=(x_1,y_1)$ 、 $Q=(x_2,y_2)$ ，不妨 $x_1 \le x_2$ 。“能用一段满足角度约束的线段把 $Q$ 接在 $P$ 后面”，精确条件就是

|y_2 - y_1| \le x_2 - x_1

夹角 $\le 45^\circ$ 嘛，斜率绝对值就 $\le 1$ ，竖直跨度不能超过水平跨度。

边界要钉一刀： $x_1 = x_2$ 时退化成 $|\Delta y| \le 0$ ，即 $P,Q$ 同点——所以两个不同的同 $x$ 点永远进不了同一条折线（左到右的折线对 $x$ 严格单调）。后面实现的并列处理会用到这点。

第二步：45° 旋转，变成二维支配

把绝对值拆成两条同时成立的不等式：

y_2 - y_1 \le x_2 - x_1 \quad\text{且}\quad y_1 - y_2 \le x_2 - x_1

两条都做纯移项，让 $P$ 和 $Q$ 彻底分到不等号两侧，冒出来两个组合量。令

\textcolor{blue}{\boldsymbol{u = x + y}}, \qquad \textcolor{blue}{\boldsymbol{v = x - y}}

条件就清爽成了 $u_P \le u_Q$ 且 $v_P \le v_Q$ 。

这里有个 易错点 ：是 不下降（ $\le$ ，含等号） ，不是"严格上升"。反例 $P=(0,0)$ 、 $Q=(1,1)$ ： $u$ 从 0 升到 2， $v$ 从 0 到 0 没变；但 $|\Delta y| = 0 \le \Delta x = 1$ ， $Q$ 完全能接在 $P$ 后面。按"严格"就会误判。

几何上：第一步那个从 $P$ 朝右张开的 $90^\circ$ 锥形，换到 $(u,v)$ 系里锥的两条边正好贴着新坐标轴，能接就变成最干净的一句—— $Q$ 落在 $P$ 的右上方（含边界），标准的二维支配。

第三步：一条折线 = 一条链 → 最小链覆盖

把 pair 关系抬到整条折线：一条平直折线经过的那串点，按经过顺序看， $(u,v)$ 两维都单调不减——这就是 $(u,v)$ 支配偏序里的一条链。

按 $(u,v)$ 字典序排序（ $u$ 升，同 $u$ 则 $v$ 升——这个并列方向正好让同 $u$ 的点能进同一条链，不会被错算）。排完抽出 $v$ 序列，一条折线就对应 $v$ 的一个 非降子序列 。于是整道题变成：用最少个 " $v$ 非降子序列" 覆盖整条 $v$ 序列。

第四步：Dilworth / 导弹拦截

“用最少个非降子序列覆盖一个序列”——这正是导弹拦截那道经典题的对偶。由 Dilworth 定理：

关键结论：最少非降子序列覆盖数 = 该序列的最长严格下降子序列长度。

所以答案 = $v$ 序列的最长严格下降子序列长度。实现上不用真去求"下降"：把 $v$ 取负，求 $-v$ 的 最长严格上升子序列 （patience sorting / lower_bound ， $O(n\log n)$ ）即可。

📎 动画与源码

完整推导对话录（含锥形配图、 $(u,v)$ 支配区配图、Dilworth 方向对照表）见页面末尾附件的 mentor.pdf ；完整 AC 源码见下方 AC 代码 折叠块，也在附件里附了 .cpp.txt 方便复制对拍。

AC 代码

AC 提交（vjudge）

源码较长（自带几何模板 + LIS 类），完整 C++ 折叠在下方；同一份也作 .cpp.txt 附件挂在页面末尾。

展开完整 C++ 源码

// teamname: Gospel_rock
/**
 * Problem: P5939 [POI 1998 R3] 折线
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P5939
 * Created: 2026-05-19 16:10:16
 * 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, INF = (1ll << 61) - 1;
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
 */

// 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));
	}
}

// x*x 安全平方: 整数升 i128 防溢出 (1000^2 不会溢, 但模板要扛 1e9 量级输入),
// 浮点原样 T*T 不动 (i128 没浮点意义).
template<class T>
auto squared(T x) {
	if constexpr (is_floating_point_v<T>) {
		return x * x;
	} else {
		return (i128)x * (i128)x;
	}
}

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

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> 隐式 (common_type 单调升档方向, U -> T 必须无损):
	// common_type_t<U, T> == T 才放行 (例 ll -> DB 通; DB -> ll 拦, 防 truncation)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	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; }

	// 标量乘除: 返回 Point<common_type_t<T, U>> (C++14), 自动算公共类型
	// <ll,ll>=ll / <ll,DB>=DB / <DB,ll>=DB; R==T 走 copy ctor, R!=T 走 converting ctor
	template<class U>
	friend auto operator*(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r *= b;
		return r;
	}

	template<class U>
	friend auto operator*(U a, Point b) {
		Point<common_type_t<T, U> > r = b;
		r *= a;
		return r;
	}

	template<class U>
	friend auto operator/(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r /= b;
		return r;
	}

	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()); }

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

	Point<DB> rot(DB ang) const {
		return Point<DB>(cosl(ang) * x - sinl(ang) * y, sinl(ang) * x + cosl(ang) * y);
	}

	// 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, class U>
auto cross(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	//（改为这个非float，那么在类型为I128时，仍然可以计算）
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		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, class U, class V>
auto cross(Point<T> o, Point<U> a, Point<V> 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;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) · (b - o)
// 用途: 判夹角钝/直/锐 (>0 锐, =0 直, <0 钝) / 投影长度的有符号 2 倍 / 点在线段上的位置判定
template<class T, class U, class V>
auto dot(Point<T> o, Point<U> a, Point<V> b) {
	return dot(a - o, b - o);
}

// 采用两点式
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> 隐式 (common_type 单调升档方向, 同 Point converting ctor)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	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;
}

// 距离平方（不开方）：旋转卡壳里 ans 反复更新，留到最后一次 sqrt
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)});
}


// 最长 (严格 / 非严格) 上升子序列 + 还原值与下标
// 0-based 输入；strict=true → 严格递增, strict=false → 单调不降
struct LIS {
	vector<ll> a; // 输入序列
	int n;
	bool strict;
	vector<ll> tail; // patience sort: 长度-i 的子序列最小末值
	vector<int> i_len; // 以下标 i 结尾的 LIS 长度
	vector<ll> seq; // 还原的递增子序列值
	vector<int> pos; // 还原的下标 (0-based, 严格递增)

	LIS(const vector<ll> &v, bool strict_)
		: a(v), n((int)v.size()), strict(strict_), i_len(v.size(), 0) {
		tail.reserve(n);
		for (int i = 0; i < n; ++i) {
			// 严格 → lower_bound（替换首个 ≥ a[i]）
			// 非严格 → upper_bound（替换首个 > a[i]）
			auto it = strict
				          ? lower_bound(tail.begin(), tail.end(), a[i])
				          : upper_bound(tail.begin(), tail.end(), a[i]);
			if (it == tail.end()) {
				tail.push_back(a[i]);
				i_len[i] = (int)tail.size();
			} else {
				int idx = (int)(it - tail.begin());
				tail[idx] = a[i];
				i_len[i] = idx + 1;
			}
		}
		// 反向贪心还原一组解
		int need = (int)tail.size();
		seq.reserve(need);
		pos.reserve(need);
		ll cur = LLONG_MAX;
		for (int i = n - 1; i >= 0 && need > 0; --i) {
			bool ok = strict ? (a[i] < cur) : (a[i] <= cur);
			if (ok && i_len[i] >= need) {
				seq.push_back(a[i]);
				pos.push_back(i);
				cur = a[i];
				--need;
			}
		}
		reverse(seq.begin(), seq.end());
		reverse(pos.begin(), pos.end());
	}

	int size() const { return (int)tail.size(); }
};


void Solve() {
	ll N;
	cin >> N;
	vector<Point<ll> > A(N);
	for (auto &p: A) {
		cin >> p;
	}
	vector<Point<ll> > uvA(N);
	for (int i = 0; i < N; ++i) {
		auto [x,y,_] = A[i];
		uvA[i] = Point<ll>(x + y, x - y);
	}
	sort(all(uvA));
	vector<ll> uv(N);
	for (int i = 0; i < N; ++i) {
		uv[i] = -uvA[i].y;
	}
	LIS lis(uv, true);
	cout << lis.size() << "\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/69981363

*/

心路历程（一次方向写反 → AC）

Dilworth 方向写反：第一版写成 LIS(uv, false) ——求的是 $v$ 的 最长非降子序列 ，量根本不对。它和"最小链覆盖"没关系，只是在样例 1 上巧合都等于 3，没暴露。
照出 bug 的反例：输入 2 / 0 0 / 2 0 。两点 $(0,0),(2,0)$ 在同一条水平折线上（夹角 $0^\circ$ ），正解 = 1 ；错误代码： $(u,v)=(0,0),(2,2)$ ， $v$ 序列 $[0,2]$ ，最长非降 = 2 → 输出 2 ，错。
修法：改成求 $v$ 的最长严格下降子序列——uv[i] = -uvA[i].y; 取负后 LIS(uv, true); （strict 走 lower_bound ），等价于求最长严格下降。一发 AC。
沉淀的易错点：(1) Dilworth 是"最少非降覆盖 = 最长 严格下降 “，方向 / 严格性都不能错；(2) 支配条件是"不下降"含等号，不是"严格上升”，同 $u$ / 同 $v$ / 重点都得能进同一条链；(3) 排序并列方向（同 $u$ 按 $v$ 升）要和"求严格下降"配套，弄反会把可同链的点错算成反链。

附件

下面附件均已直接传入本页面，可在 Notion 内直接预览：

mentor.pdf —— 完整带教对话录（PDF 版），含 5 步推导 + 锥形 / 支配区 TikZ 配图 + Dilworth 方向对照表 + 反例。
P5939_POI_1998_R3_.cpp.txt —— 完整 AC 源码（下载后改回 .cpp ，含几何模板 + LIS 类，方便复制对拍）。

完整带教对话录(PDF): 5 步推导 + 锥形/(u,v)支配区 TikZ 配图 + Dilworth 方向对照表 + 反例

P5939_POI_1998_R3_.cpp.txt

洛谷 P1742 - 最小圆覆盖

Posted on 2026-05-19

题目大意

洛谷 P1742 最小圆覆盖：给 $N$ 个平面点（ $N\le 10^5$ ，坐标实数），求一个半径最小、且能把所有点都包住（含边界）的圆，第一行输出半径、第二行输出圆心坐标，精度 $10^{-9}$ 。

样例

6 个点 (8,9) (4,7.5) (1,2) (5.1,8.7) (9,2) (4.5,1) → 半径 5、圆心 (5,5)。这个圆恰由 (8,9)、(1,2)、(9,2) 三点的外接圆决定，其余 3 点严格在内部——暗示了最小圆由至多 3 个边界点钉死。

思路讲解

一句话

随机增量法（Welzl）：当前圈外的点必落在新圈边界上，于是逐点加入、三层钉点维护当前最小圆，期望 $O(N)$ 。这道题真正的坑不在算法本身，在内层 for j / for k 必须升序——内层判定下标改对了、循环方向写反，照样直接 WA。

Welzl 灵魂：引理 + 自由度 + 前缀不变量

内核一句话：圈外点 ⇒ 必在新最小圆边界上（圆内部容不下它、又必须刚好罩住它）。每钉一个边界点，圆的自由度 $-1$ ：3 自由度 → 钉 $p_i$ 剩 2 → 钉 $p_j$ 剩 1（圆心锁在中垂线上）→ 钉 $p_k$ 剩 0（三点外接圆唯一）。

**关键不变量：**每层 $res$ = 「覆盖前缀 $p_0\dots p_{t-1}$ + 已钉点」的最小圆。正确性全靠它。

三层：L0 钉 0 点扫 $i$ ；L1 钉 $p_i$ 扫 $j$ ；L2 钉 $p_i,p_j$ 扫 $k$ ，谁在圈外就 res = 外接圆。随机打乱只把复杂度降到期望 $O(N)$ ，与正确性无关。

三层结构（核心循环，升序版）

template<class T>
Circle<DB> min_circle_cover(vector<Point<T> > A) {
	// 先打乱
	shuffle(all(A), rng);
	Circle<DB> res(A[0], 0);
	for (int i = 1; i < SZ(A); ++i) {
		if (!res.is_point_in_circle(A[i])) {
			res = Circle<DB>(A[i], 0);
			// 注意，我们的这个后缀点之前已经考虑过了，实际上我们是要覆盖前缀点
			for (int j = 0; j < i; ++j) {
				if (!res.is_point_in_circle(A[j])) {
					res = circle_from_diameter(A[i], A[j]);
					for (int k = 0; k < j; ++k) {
						if (!res.is_point_in_circle(A[k])) {
							res = outcircle_triangle(A[i], A[j], A[k]);
						}
					}
				}
			}
		}
	}
	return res;

⚠️ 内层必须升序，倒序为什么 WA（本题关键）

升序让「已扫过的点」恒等于引理担保仍在圈内的「前缀」 $\{p_0\dots p_{j-1}\}$ ，两集合重合、归纳一步步闭合。

倒序时（for(j=i-1;j>=0;--j)）：在某个 $j$ 处重建圆，引理只担保覆盖前缀 $p_0\dots p_{j-1}$ ；但你实际已扫过的是后缀 $p_{j+1}\dots p_{i-1}$ （大下标先遍历）。这批后缀点没人保证还在新圈里，而 $j$ 只减不回头、永不复查 → 被甩出就永久丢失。

**同样例 6 点实测：**升序连跑 30/30 全 = $r{=}5$ 、圆心 (5,5)。
倒序飘忽： $r{=}5$ （对） / $r{=}6.23$ 圆心 (5,9.375)（盖住但非最小 = WA） / $r{=}3.876$ 圆心 (7.05,5.35)（连 (1,2) 都没盖 = 非法解）。
**两种坏法：**漏点（已扫点被甩出 → 非法），或后续 circle_from_diameter 重置把圆撑大（非最小）。

🎬 Note: 交互式演示：下面 3 张关键帧出自 mc_order_demo.html（完整可交互版在末尾「附件」，可自己点 Step、切升/倒序、拖引理点、滑前缀/后缀滑条）。

📎 动画与源码

完整可交互 HTML 演示、AC 源码、完整带教对话录 PDF 都在页面末尾「附件」节，直接点开 / 下载。

AC 代码

AC 提交链接：vjudge.net/solution/69974356

展开完整 C++ 源码

// teamname: Gospel_rock
/**
 * Problem: P1742 最小圆覆盖
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P1742
 * Created: 2026-05-18 17:16:40
 * 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, INF = (1ll << 61) - 1;
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
 */

// 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));
	}
}

// x*x 安全平方: 整数升 i128 防溢出 (1000^2 不会溢, 但模板要扛 1e9 量级输入),
// 浮点原样 T*T 不动 (i128 没浮点意义).
template<class T>
auto squared(T x) {
	if constexpr (is_floating_point_v<T>) {
		return x * x;
	} else {
		return (i128)x * (i128)x;
	}
}

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

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> 隐式 (common_type 单调升档方向, U -> T 必须无损):
	// common_type_t<U, T> == T 才放行 (例 ll -> DB 通; DB -> ll 拦, 防 truncation)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	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; }

	// 标量乘除: 返回 Point<common_type_t<T, U>> (C++14), 自动算公共类型
	// <ll,ll>=ll / <ll,DB>=DB / <DB,ll>=DB; R==T 走 copy ctor, R!=T 走 converting ctor
	template<class U>
	friend auto operator*(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r *= b;
		return r;
	}

	template<class U>
	friend auto operator*(U a, Point b) {
		Point<common_type_t<T, U> > r = b;
		r *= a;
		return r;
	}

	template<class U>
	friend auto operator/(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r /= b;
		return r;
	}

	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()); }

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

	Point<DB> rot(DB ang) const {
		return Point<DB>(cosl(ang) * x - sinl(ang) * y, sinl(ang) * x + cosl(ang) * y);
	}

	// 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, class U>
auto cross(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	//（改为这个非float，那么在类型为I128时，仍然可以计算）
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		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, class U, class V>
auto cross(Point<T> o, Point<U> a, Point<V> 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;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) · (b - o)
// 用途: 判夹角钝/直/锐 (>0 锐, =0 直, <0 钝) / 投影长度的有符号 2 倍 / 点在线段上的位置判定
template<class T, class U, class V>
auto dot(Point<T> o, Point<U> a, Point<V> b) {
	return dot(a - o, b - o);
}

// 采用两点式
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> 隐式 (common_type 单调升档方向, 同 Point converting ctor)
	template<class U, enable_if_t<is_same_v<common_type_t<U, T>, 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;
}

// 距离平方（不开方）：旋转卡壳里 ans 反复更新，留到最后一次 sqrt
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)});
}

// ===== 圆 (Circle) =====

// 圆弧 from -> to 的逆时针弧角差 [0, 2pi), 不是 abs(to - from)
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;
}

enum CircleRelation {
	// 表示这个公切线个数; COINCIDENT (-1) 是重合 sentinel (无穷多公切线)
	COINCIDENT = -1,
	ONE_CONTAINS_OTHER = 0,
	INTERNALLY_TANGENT = 1,
	INTERSECTING = 2,
	EXTERNALLY_TANGENT = 3,
	EXTERNALLY_APART = 4,
};

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 不限定范围 (允许负值 / > 2pi), 始终走 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));
	}

	template<class U>
	bool is_point_in_circle(const Point<U> &p) {
		return distancePPNorm(p, c) <= squared(r);
	}

	friend istream &operator>>(istream &is, Circle &c) {
		is >> c.c >> c.r;
		return is;
	}

	// 用于 debug
	friend ostream &operator<<(ostream &os, Circle &c) {
		os << "<" << c.c << "," << c.r << ">";
		return os;
	}
};

// 两点为直径的圆: 圆心为两点中点, 半径为两点距离的一半
// 退化 (两点重合): 半径为 0, 圆心即该点 (退化为点, 是合法结果, 非 sentinel)
Circle<DB> circle_from_diameter(Point<DB> a, Point<DB> b) {
	return Circle<DB>((a + b) / 2, distancePP(a, b) / 2);
}

// === incircle_triangle + outcircle_triangle (espanso :incircleOutcircle, 拆自 :Circle)
//     依赖: :Point + :Circle
// 三角形内接圆: 圆心为加权重心 (权 = 对边长), 半径 = min(圆心到三边距离)
// 退化 (共线 / 任意两点重合, cross == 0): 内接圆不存在, 返回 r=0 sentinel (圆心位置无意义)
// AC https://vjudge.net/solution/69920478 (CGL_7_B)
Circle<DB> incircle_triangle(Point<DB> a, Point<DB> b, Point<DB> c) {
	if (sgn(cross(a, b, c)) == 0) return Circle<DB>(a, 0);
	DB ab = distancePP(a, b), ac = distancePP(a, c), bc = distancePP(b, c);
	Point<DB> I = (a * bc + ac * b + ab * c) / (ab + ac + bc);
	return Circle<DB>(I, min({distancePS(I, Line(a, c)), distancePS(I, Line(a, b)), distancePS(I, Line(b, c))}));
}

// 三角形外接圆: 圆心是两条边的垂直平分线交点
// 退化 (共线 / 任意两点重合, cross == 0): 外接圆不存在, 改返回覆盖三点的最小圆 (以最远点对为直径)
// AC https://vjudge.net/solution/69927652 (CGL_7_C)
Circle<DB> outcircle_triangle(Point<DB> a, Point<DB> b, Point<DB> c) {
	if (sgn(cross(a, b, c)) == 0) {
		DB ab = distancePP(a, b), ac = distancePP(a, c), bc = distancePP(b, c);
		if (ab >= ac && ab >= bc) return circle_from_diameter(a, b);
		if (ac >= bc) return circle_from_diameter(a, c);
		return circle_from_diameter(b, c);
	}
	Point<DB> abMid = (a + b) / 2, acMid = (a + c) / 2;
	Point<DB> vecAb = (b - a).rot90(), vecAc = (c - a).rot90();
	Point<DB> I = getintersect(Line(abMid, abMid + vecAb), Line(acMid, acMid + vecAc));
	return Circle<DB>(I, distancePP(I, a));
}

// AC https://vjudge.net/solution/69974356 最小圆覆盖
template<class T>
Circle<DB> min_circle_cover(vector<Point<T> > A) {
	// 先打乱
	shuffle(all(A), rng);
	Circle<DB> res(A[0], 0);
	for (int i = 1; i < SZ(A); ++i) {
		if (!res.is_point_in_circle(A[i])) {
			res = Circle<DB>(A[i], 0);
			// 注意，我们的这个后缀点之前已经考虑过了，实际上我们是要覆盖前缀点
			for (int j = 0; j < i; ++j) {
				if (!res.is_point_in_circle(A[j])) {
					res = circle_from_diameter(A[i], A[j]);
					for (int k = 0; k < j; ++k) {
						if (!res.is_point_in_circle(A[k])) {
							res = outcircle_triangle(A[i], A[j], A[k]);
						}
					}
				}
			}
		}
	}
	return res;
}


void Solve() {
	ll N;
	cin >> N;
	vector<Point<DB> > A(N);
	for (auto &p: A) {
		cin >> p;
	}
	auto ansc = min_circle_cover(A);
	cout << fsp(12) << ansc.r << "\n" << ansc.c.x << " " << ansc.c.y;
}

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/69974356

*/

心路历程（WA → AC）

**第一次：**内层判定误写成 A[i] 而非 A[j] / A[k]，res 退化成半径 0 的点圆，只要有点在外答案就全错。
**改对下标后仍 WA：**内层循环写成了倒序 for(j=i-1;j>=0;--j) / for(k=j-1;k>=0;--k)。
**现象飘忽：**同样例点不同 shuffle 跑出 r=5（对）、r=6.23（盖住但非最小=WA）、r=3.876（连 (1,2) 都没盖=非法），一开始以为是精度/eps 问题，其实是结构错。
**根因：**倒序破坏「前缀不变量」——引理重建只担保前缀，倒序实际已扫的是后缀，被甩出的点 j 只减不回头、永不复查。
**修复：**内层改升序 for(j=0;j<i;++j) / for(k=0;k<j;++k)，固定样例点序回归 30/30 稳定 r=5、圆心 (5,5)。

**教训：**随机增量法的正确性不靠随机（随机只管期望复杂度），靠「已扫集合恒为前缀」这条不变量；扫描方向本身是正确性的一部分，不是风格选择。

附件

本题相关产物（可直接点开 / 下载）：

mentor.tex.txt

P1742_mini_circle.cpp.txt

Gym 105173 M - House

Posted on 2026-05-18

题目大意

比赛：The 2024 CCPC National Invitational Contest (Northeast) / The 18th Northeast Collegiate Programming Contest（2024 CCPC 东北邀请赛 / 第 18 届东北赛区）

原题链接：Gym-105173 M House（vjudge）｜ CF Gym 原题

AC 提交：vjudge submission 69955475

题面

平面上给定 $n$ 个互不相同的整点，从中选 5 个不同的点 $(A, B, C, D, E)$ 组成一个 “房子”：

$ABCD$ 是一个矩形（按顺序，即 $AB \parallel CD$ 、 $AD \parallel BC$ 、 $AD \perp AB$ ）
$CDE$ 是以 $CD$ 为底的等腰三角形（ $|CE| = |DE|$ ）
$E$ 在 $CD$ 直线远离 $AB$ 那一侧（数学条件： $\overrightarrow{DA} \cdot \overrightarrow{DE} < 0$ ）

两个房子被认为不同当且仅当存在至少一个点的坐标不同（按点集判，不按 tuple 顺序）。问能凑出多少个不同的房子。

数据范围

$5 \le n \le 300$
$|x_i|, |y_i| \le 10^9$ （整数坐标）

样例

样例 2： $n = 7$ ，点集 $\{(0,2), (4,0), (2,4), (0,0), (2,0), (4,4), (4,2)\}$ ，答案 $= 5$ 。

思路讲解

一句话

$n \le 300$ 给 $O(n^3)$ 留足空间。把"枚举 5 个点"压缩为"枚举矩形/三角形共享的那条底边 $(C, D)$ "，剩下 $A$ 和 $E$ 各自独立地在 $C, D$ 限定的两条特定直线上检查——一对底边 $O(n)$ 扫一遍点就够了。

关键观察：把 5 元组解耦成两个 1 元组

5 个点同时枚举是 $O(n^5)$ ，连暴力的边都摸不到。关键观察：把 $C, D$ 当主角，固定 $(C, D)$ 这条底边后：

$A$ 必须满足 $AD \perp CD$ 且 $B = A + (C - D)$ 也在点集 —— $A$ 完全由"在过 $D$ 的垂线上 + $B$ 是否凑得齐"决定，跟 $E$ 无关
$E$ 必须满足 $|CE| = |DE|$ ，即 $E$ 在 $CD$ 的中垂线上 —— 跟 $A$ 也无关
唯一耦合的条件是" $A$ 和 $E$ 在 $CD$ 异侧"

于是只要固定 $(C, D)$ ，把 $A$ 候选和 $E$ 候选按所在侧别分桶，最后一组 $A$ 桶 $\times$ 异侧的 $E$ 桶就是这一对 $(C, D)$ 的贡献。

7 个点的样例 —— 看上去能拼出几个？官方答案是 5 个。

算法骨架（ $O(n^3)$ ）

枚举有序对 $(C, D)$ （ $O(n^2)$ 对），对每一对扫一遍剩下 $n - 2$ 个点 $P$ ，做两个 $O(1)$ 判定：

判定	条件	归类
$P$ 能当 $A$ 吗？	$(P - D) \cdot (C - D) = 0$ 且 $P + (C - D)$ 也在点集	按 $\mathrm{cross}(C - D, P - D)$ 符号 → $A_L$ / $A_R$
$P$ 能当 $E$ 吗？	$\	P - C\	^2 = \	P - D\	^2$ （在 $CD$ 中垂线上）	按同一 cross 符号 → $E_L$ / $E_R$

这一对 $(C, D)$ 的贡献是 $A_L \cdot E_R + A_R \cdot E_L$ ——把 $A$ 和 $E$ 强行配到 $CD$ 两侧。

关键不变量：异侧 = $\mathrm{cross}(C - D, P - D)$ 符号相反，等价于点积 $\overrightarrow{DA} \cdot \overrightarrow{DE} < 0$ 那个题面条件，但 cross 是整数运算不会出精度。

$A$ 候选的两条轨迹 + $E$ 候选的一条轨迹

固定 $(C, D)$ 之后，几何直观特别清晰：

绿色虚线（两条）：过 $C, D$ 各画一条 $\perp CD$ 的垂线 —— $A$ 必在过 $D$ 那条上， $B$ 必在过 $C$ 那条上
紫色虚线（一条）： $CD$ 的中垂线 —— $E$ 必在它上面
按每个候选点落在 $CD$ 哪一侧（cross 的符号）分到 $L$ / $R$ 桶里

算法等价于"按轨迹切片 + 异侧匹配"。

关于"为何要除以 2 / 为何 cpp 没除"

HTML demo 走的版本是有序对 $(C, D)$ 枚举， $(C, D)$ 和 $(D, C)$ 数同一个房子两次，最后 $\div 2$ 。

AC 的 cpp 走的是无序对 $\{c_i, d_i\}$ （for ci，for di = ci + 1），固定一个方向 $(c, d)$ ，但用 $A_L \cdot E_R + A_R \cdot E_L$ 自动把两侧都数了进去 —— 每个房子恰好数一次，不用除 2 。两种写法等价，cpp 这种省去末尾 $/ 2$ 一步。

复杂度 + 溢出注意

复杂度： $O(n^2)$ 对 $\times$ $O(n)$ 扫点 $= O(n^3)$ 。 $n = 300$ 时约 $2.7 \times 10^7$ 次基本操作，常数小，稳过
点集查询用 unordered_map<pair<ll,ll>, int> 或先排序后二分都行（cpp 走的是 sort + binary_search）
溢出：坐标到 $10^9$ 。判 $E$ 的 $|P - C|^2 - |P - D|^2 = -(C - D) \cdot (2P - C - D)$ 展开后内部乘积量级 $4 \times 10^{18}$ ，两项加和会越界 long long 。用 __int128 即可（模板里 dot / cross 在整数路径下已经 promote 到 __int128，直接调）

📎 交互式 demo

下方"附件"节挂了 house_count.html.txt —— 下载后改回 .html 用浏览器打开，可以一步步点 下一步 看每一帧的判定过程（15 帧覆盖：7 点初始 → 5 个房子轮播 → 算法枚举 (C, D) → 5 个候选点逐个分桶 → 汇总贡献 → 求和 ÷ 2 的全流程）。

AC 代码

AC 提交链接：vjudge submission 69955475

核心 Solve() 函数（完整代码见下方附件 House_Count.cpp.txt）：

展开 Solve() 核心实现

void Solve() {
    ll N;
    cin >> N;
    vector<Point<ll>> A(N);
    for (auto &p : A) cin >> p;
    sort(all(A));                                  // 为后面 binary_search 准备
    ll ans = 0;
    for (int ci = 0; ci < N; ++ci) {
        for (int di = ci + 1; di < N; ++di) {
            // 固定无序对 {ci, di}, 把 c = A[ci], d = A[di] 当方向
            vector<ll> cntE(2), cntA(2);
            for (int xi = 0; xi < N; ++xi) {
                if (xi == di || xi == ci) continue;
                auto [c, d, x] = make_tuple(A[ci], A[di], A[xi]);
                auto vecCd = c - d;
                // 跳过共线点 (cross = 0): A / E 要严格在两侧
                if (sgn(cross(vecCd, x - d)) == 0) continue;

                // 判 E: |xd|^2 == |xc|^2 <=> x 在 CD 中垂线上
                if (distancePPNorm(x, d) == distancePPNorm(c, x)) {
                    if (sgn(cross(vecCd, x - d)) < 0) cntE[0]++;
                    else                              cntE[1]++;
                }

                // 判 A: (c-d) ⊥ (x-d) 即 dot == 0, 且 B = x + (c-d) 在点集
                if (sgn(dot(vecCd, x - d)) == 0) {
                    auto b = vecCd + x;
                    if (binary_search(all(A), b)) {
                        if (sgn(cross(vecCd, x - d)) < 0) cntA[0]++;
                        else                              cntA[1]++;
                    }
                }
            }
            // A 在一侧, E 在另一侧 -> 强制异侧
            ans += cntE[0] * cntA[1];
            ans += cntE[1] * cntA[0];
        }
    }
    cout << ans << "\n";
}

心路历程

5 个点同时枚举想都别想： $O(n^5) = 2.4 \times 10^{12}$ ，肯定要解耦。题目让 $(A, B, C, D, E)$ 5 个点中 $C, D$ 同时是矩形的边和三角形的底 → 自然以 $C, D$ 为主角， $A, B, E$ 都跟着定下来
$B$ 是被 $A$ 顺便确定的：注意 $B - A = C - D$ （矩形对边等长平行），所以扫到一个 $A$ 候选时立刻知道 $B$ 应该在哪，查一次点集即可 —— 不用单独枚举 $B$
异侧条件靠 cross 符号实现：题面给 $\overrightarrow{DA} \cdot \overrightarrow{DE} < 0$ 看起来是浮点不等式，但本质就是 " $A, E$ 在 $CD$ 直线两侧"，等价于 $\mathrm{cross}(C - D, P - D)$ 异号 —— 整数判完美
有序对 vs 无序对：第一次写很容易写成有序对枚举然后忘了 $\div 2$ ，或者无序对枚举但只算 $A_L \cdot E_R$ 漏数一半。核心是想清楚 $\{c, d\}$ 作为无序对枚举一次后， $A_L E_R + A_R E_L$ 已经覆盖了 $A$ 在两侧 × $E$ 在异侧的全部 4 种 (label, side) 组合，等价于有序对求和后 $\div 2$
溢出 __int128：坐标 $10^9$ 平方 $10^{18}$ 还在 long long 内，但两个平方相减 / 相加到 $4 \times 10^{18}$ 就溢了。模板里 cross / dot / Point::norm() 整数路径下自动走 __int128，所以直接调 distancePPNorm 比较两个 __int128 就行，不用手动加 (__int128) 强转
点集查询用 sort + binary_search： $n \le 300$ 完全没必要上 unordered_map<pair<ll,ll>> ， sort + binary_search<Point<ll>> 走默认 operator<（先 x 后 y）就够了，常数还更小

附件

完整 AC 源码（含中文注释，下载后改回 .cpp 用 g+±15 编译）：

House_Count.cpp.txt

交互式 HTML demo（15 帧讲解动画，解压得到 house_count.html，用浏览器打开点下一步逐帧看）：

house_count_html.zip

CCPC 河南 2025 L - Astral Decay

Posted on 2026-05-16

vjudge 链接 · Codeforces Gym 原题 · 2025 CCPC 河南省赛 & 全国邀请赛（郑州，黄河科技学院）

题目大意

二维平面上 n 个互不相同的点（1 ≤ n ≤ 6666，坐标 |x|, |y| ≤ 10⁹）。从这 n 个点中有放回地选 3 个点，标记为 A, B, C，最小化点积：

\overrightarrow{AB} \cdot \overrightarrow{AC} = (x_B - x_A)(x_C - x_A) + (y_B - y_A)(y_C - y_A)

A, B, C 可以选相同的点，所以答案的下界是 0（取 A = B = C 任意点都给 0）。

输入 / 输出 / 数据范围

第 1 行：n（1 ≤ n ≤ 6666）
后 n 行：每行 x y（|x|, |y| ≤ 10⁹）
输出一行一个整数，最小点积（可能为负，需要 long long / int128）

样例 1

输出 -8（最优 A = p5 = (0, -1)（hull 内部点）、B = p3 = (3, 0)、C = p4 = (-3, 0)，dot = 3·(-3) + 1·1 = -8）。

思路讲解

一句话

凸包 + 双指针的「投影版」：B、C 都在凸包上（调整法证），固定 A 后让 B 沿 hull CCW 走、C 用双指针单调跟进。整体 O(n·h) ≤ O(n²)。

⚠️ 关键边界（test 44 WA 根因）：A 在凸包顶点上时，B 的起点必须是 A 的 CCW 后继 A_next，不能从 hull[0] 起步——否则方向序断层破坏双指针单调性。光「跳过 B = A」治标不治本。

把"最小点积"翻译成"在某方向上最极端"

固定 A，把点积写成投影形式：

\overrightarrow{AB} \cdot \overrightarrow{AC} = |\overrightarrow{AB}| \cdot \mathrm{proj}_{\overrightarrow{AB}}(\overrightarrow{AC})

其中 proj 是 AC 在方向 AB 上的有向投影长度（同向为正、反向为负）。要让点积越负越好，就要让 AC 在方向 -AB 上的距离越远越好。

关键不变量：凸集上线性函数的极值在顶点取到。所以最优 C 必然在凸包上；对称地 B 也在凸包上。

但 A 自己不一定在凸包上！ 样例 1 的最优 A = (0, -1) 就在 hull 内部（题目唯一的内部点）。这是「必须枚举所有原始点当 A、不能只在 hull 上枚举 A」的原因——一个非常容易写错的实现细节。

算法三阶段

阶段	干什么	跳过的代价
1. 凸包预处理	对全部 n 个点跑 Andrew O(n log n)	B/C 在全集枚举 → O(n³) TLE
2. 枚举 A	对原始点集（不是 hull）每点当 A	只在 hull 上枚举 A → 漏内部最优 A（样例 1 答案变 -7 而不是 -8）
3. 双指针扫 (B, C)	固定 A 后 B 沿 hull CCW 走、C 单调跟进	二重循环 → O(n·h²) 大数据 TLE

阶段 2 / 3 的「分裂」是核心理解点：枚举的是原始点（n 个），扫的是凸包上的点（h 个），两者不一样。

双指针单调性 = 旋转卡壳的对偶

固定 A，写出内层「对 B 求 C」函数：

C^*(B) = \arg\min_{C \in H}\; \overrightarrow{AB} \cdot \overrightarrow{AC} = \arg\min_{C \in H}\; |\overrightarrow{AB}| \cdot \mathrm{proj}_{\overrightarrow{AB}}(\overrightarrow{AC})

C*(B) 就是凸包在方向 -AB 上的支撑点。

灵魂对偶：本题就是旋转卡壳的「投影版」——卡壳卡的是「到边的距离」，本题卡的是「沿方向的有向投影」，主结构同构。

结构件	旋转卡壳（求直径）	本题（最小点积）
主循环对象	凸包边 `e_i`	凸包顶点 B（视作方向 AB）
跟进对象	对踵点 `C*`（离 `e_i` 最远）	支撑点 `C*`（方向 `-AB` 上最远）
单调性根源	`e_i` 法方向沿 H 单调旋转	AB 方向随 B 沿 H 单调旋转
判定工具	cross 比 C 到边距离	dot 比 C 沿 AB 投影

A 在凸包上时的边界处理（test 44 WA 根因）

这一节是 ICPC 题解里最容易写错的点，也是题解 PDF 一笔带过那句的真意：

如果 A 在凸包上，枚举 B 时就不要枚举 A 了，从 A 的下一个点开始枚举 B，转回来到 A 的上一个点结束枚举。 —— 命题组 sol.pdf

为什么不能"光跳过 B = A"了事

if (A.id == convex[b].id) continue; 只解决 AB = 0 退化（该轮 dot 全是 0），没解决方向序断层。

真正的死因：双指针单调性要求「随 B 沿 hull 走，方向 AB 必须单调旋转」，这样 C* 才能跟着单向推进。当 A 在 hull 顶点 h_{i_A} 上时，按 hull 原序 [h_0, h_1, ..., h_{h-1}] 遍历 b：

h_0, h_1, ..., h_{i_A - 1} 这一段在「从 A 看的 CCW 极角序」里属末段
真正的 CCW 起点是 h_{i_A + 1}（A 的 next）

代码从 h_0 起扫等于「方向倒着来」，下一步跳到 h_{i_A + 1} 时方向回退 90° 以上，C* 单向 c++ 跟不上 → WA。

实证反例（17 点，本会话抓到）

真最优：A = p11 = (-97, -14)（hull[1]）、B = p6 = (-30, -94)（hull[4]）、C = p14 = (-61, 83)（hull[14]），dot = -5348。

「只 continue 跳过 b=A」的错代码输出 -5338，差 10——正是 b = h0 方向 ≈ +92.5° → b = h2 方向 ≈ -73°，方向断层 165° 让 c 跟丢了 c = h14。

正确修法

// 找 A 在 hull 上的位置 aPos (-1 = 不在 hull 上)
int aPos = -1;
for (int i = 0; i < H; ++i)
    if (A[a].id == convex[i].id) { aPos = i; break; }
int bStart = (aPos == -1) ? 0 : (aPos + 1) % H;
int bCnt   = (aPos == -1) ? H : H - 1;

// 初始 c 以 convex[bStart] 为 b 基准 (不是 convex[0]!)
int c = bStart;
ll tar = dot(A[a], convex[bStart], convex[c]);
for (int i = 0; i < H; ++i) {
    ll lans = dot(A[a], convex[bStart], convex[i]);
    if (lans < tar) { tar = lans; c = i; }
}

for (int t = 0; t < bCnt; ++t) {
    int b = (bStart + t) % H;
    auto check = [&]() {
        return dot(A[a], convex[b], convex[c % H]) >=
               dot(A[a], convex[b], convex[(c + 1) % H]);
    };
    while (check()) c++;
    ans = min(ans, (ll) dot(A[a], convex[b], convex[c % H]));
}

3 个改动：

bStart = (aPos + 1) % H：让 b 从真正的 CCW 起点开始
bCnt = H - 1：走 h-1 步绕回 A_prev 终止（A 自己天然跳过）
check 用 >= 而不是 >：dot 平台时推到末尾，避免 c 卡在平台前段让下一个 b 跟不上

「为什么 hull[0] 是幸运 case」

如果 A = h0（hull 最左下顶点），那 A_next = h1——代码从 b = h0 起扫，第一轮 b = A 直接被 continue 跳，第二轮 b = h1 恰好就是真正的 CCW 起点，方向断层不出现。这就是为什么「只 continue 跳过 b=A」的写法样例 1 过了（样例 1 hull 是矩形 + 内部点，所有 hull 顶点对称，A 在内部时根本没断层；A 在 hull 上时恰好都是 hull[0] 的对称 case，运气好）。

但样例不能覆盖「A 在 hull 上但不是 hull[0]」这种邪恶 case——test 44 就是用这个数据。

📎 动画与源码

下面 3 张截图（位于「附件」节）来自 astral_decay_demo.html 的关键帧。HTML 本体在附件节末尾（zip 包，解压后用浏览器打开 .html = 完整交互演示，含 4 个 mini-demo + 主算法 step-by-step）。

AC 代码

AC 提交链接（Codeforces Gym 105941） 见 vjudge submission 记录

完整 .cpp 含 700 行几何模板 + 50 行 Solve()。完整源码见附件 Astral_Decay.cpp.txt（下载后改回 .cpp）。下面只展开核心 Solve()：

展开 Solve() 函数核心（修正后版本）

void Solve() {
    ll N;
    cin >> N;
    vector<Point<ll>> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        A[i].id = i;
    }
    auto convex = make_convex_hull(A, true, HULL_FULL);
    ll H = SZ(convex);
    ll ans = 0;  // A=B=C 给 0, 安全下界
    for (int a = 0; a < N; ++a) {
        // 找 A[a] 在 hull 上的位置, b 起点设为 A_next
        int b = 0;
        for (int i = 0; i < H; ++i) {
            if (A[a].id == convex[i].id) {
                b = (i + 1) % H;
                break;
            }
        }
        // 初始化 c: 以 convex[b] 为 b 基准找最优 c
        int c = 0;
        do {
            ll tar = dot(A[a], convex[b % H], convex[c]);
            for (int i = 0; i < H; ++i) {
                ll lans = dot(A[a], convex[b % H], convex[i]);
                if (lans < tar) { c = i; tar = lans; }
            }
        } while (false);
        // 双指针扫 H 步 (A 在 hull 上时第 1 轮 b=A 被 continue 跳, 剩 H-1 轮)
        for (int i = 0; i < H; ++i) {
            if (A[a].id == convex[b % H].id) { ++b; continue; }
            auto check = [&]() {
                return dot(A[a], convex[b % H], convex[c % H]) >=
                       dot(A[a], convex[b % H], convex[(c + 1) % H]);
            };
            while (check()) c++;
            ans = min(ans, (ll) dot(A[a], convex[b % H], convex[c % H]));
            ++b;
        }
    }
    cout << ans << "\n";
}

心路历程（WA → AC）

按真实的 debug 过程列：

第一版按题解写：枚举 A、b 沿 hull 走 h 步、c 双指针。样例 1 过，WA on test 44。
加 if (A.id == convex[b].id) continue; 跳过 b = A 退化轮。样例 1 仍过，仍 WA on test 44。
cyaron 风格 stress test：本机 gen 17~30 点全在 hull 上的随机数据（椭圆采点 + 强制 h ≥ 5）+ brute O(n³) 对拍。第 204 次种子抓到 17 点反例。
手算反例确认根因：A = p11 在 hull[1]（不是 hull[0]！），b 按 hull 顺序走方向不单调（+92.5° → -73° 回退 165°），c 单向推进跟不上。
正确修法：b 起点改 (aPos + 1) % H、走 H-1 步；c 初始扫描以 convex[bStart] 为 b 基准（不再用 convex[0]）；check 改 >=。
AC。

关键 take-away

「光看样例 AC」≠「算法正确」——样例 1 的 hull 是对称矩形 + 1 内部点，所有特殊 case（A 在 hull 上非 hull[0]）都不触发；样例 2 是随机 10 点稀疏分布，也不触发。
「跳过 b=A」是表面修法，「b 起点改 A_next****」才是治本——前者样例过但 test 44 仍 WA，后者通过。
对拍 gen 要能触发「A 在 hull 顶点上但不是 hull[0]」：均匀随机点云通常 A 在 hull 上的概率 ≈ h/n 很低；必须强制让 hull 顶点占比 ≥ 50%。本会话用的 gen：椭圆采 h ≥ 5 点 + 调过 phi/asp 让 hull 形状非对称。
几何模板里的 gen_convex_polygon 当 N ≤ 2 必死循环（N=1: j=(0+1)%1=i 让 A[i] == A[j] 永真；N=2: k=(0+2)%2=i 让 cross 三点退化恒 0）。这次顺便发现 + 修了（加 N ≤ 2 退化分支撒不重点）。

附件

astral_decay_demo.html.zip

Astral_Decay.cpp.txt

官方题解 PDF (CCPC 河南省赛 2025 全题题解, 命题组 BUAA)

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

题目大意

数据范围

样例

思路讲解

一句话

第一步：把角度约束代数化

第二步：45° 旋转，变成二维支配

第三步：一条折线 = 一条链 → 最小链覆盖

第四步：Dilworth / 导弹拦截

📎 动画与源码

AC 代码

心路历程（一次方向写反 → AC）

附件

题目大意

样例

思路讲解

一句话

Welzl 灵魂：引理 + 自由度 + 前缀不变量

三层结构（核心循环，升序版）

⚠️ 内层必须升序，倒序为什么 WA（本题关键）

📎 动画与源码

AC 代码

心路历程（WA → AC）

附件

题目大意

题面

数据范围

样例

思路讲解

一句话

关键观察：把 5 元组解耦成两个 1 元组

算法骨架（ O(n3)O(n^3)O(n3) ）

AAA 候选的两条轨迹 + EEE 候选的一条轨迹

关于"为何要除以 2 / 为何 cpp 没除"

复杂度 + 溢出注意

📎 交互式 demo

AC 代码

心路历程

附件

题目大意

输入 / 输出 / 数据范围

样例 1

思路讲解

一句话

把"最小点积"翻译成"在某方向上最极端"

算法三阶段

双指针单调性 = 旋转卡壳的对偶

A 在凸包上时的边界处理（test 44 WA 根因）

为什么不能"光跳过 B = A"了事

实证反例（17 点，本会话抓到）

正确修法

「为什么 hull[0] 是幸运 case」

📎 动画与源码

AC 代码

心路历程（WA → AC）

关键 take-away

附件

题目大意

数据范围

思路讲解

一句话

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

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

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

第 4 步：完整算法

📎 动画与源码

AC 代码

心路历程

附件

算法骨架（ $O(n^3)$ ）

$A$ 候选的两条轨迹 + $E$ 候选的一条轨迹