Gym 105158 D - 距离之比 · znzryb
> 原题:[Gym 105158 D 距离之比](https://codeforces.com/gym/105158/problem/D) | [vjudge](https://vjudge.net/problem/Gym-105158D)
> AC:[vjudge solution 69896828](https://vjudge.net/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$ 排序扫相邻对就能覆盖。所以:
1. **按** $u = x + y$ **升序排**,遍历相邻对更新最大比值
1. **按** $v = x - y$ **升序排**,遍历相邻对更新最大比值
1. 两次累计的最大值就是答案
两次 sort + 两次 $O(n)$ 扫描,单组 $O(n \log n)$ 。每对的比值直接用原 $(x, y)$ 坐标算(无需真把点替换成 $(u, v)$ )。
```cpp
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:
1. **方向决定比值** :拖一个点看比值随方向变化,验证"只看方向不看长度"
1. $xy$ ↔ $uv$ **双视图**:直观看到 $\pm 45^\circ$ 方向变 $u, v$ 轴的几何过程
1. **中值不等式三点 demo** :拖中间点 $k$ 的 $u$ 坐标,看 $s_{ij}$ 永远夹在 $s_{ik}, s_{kj}$ 之间
1. **主算法 6 点演示** :Step / Auto-play 走完两阶段排序 + 邻点扫,最优对正好在 P1-P2(u 都等于 7,Δu = 0,方向沿 v 轴 → 比值取到 $\sqrt{2}$ 上限)
HTML 本体 + 3 张关键帧截图都嵌在「附件」节里。
# AC 代码
[**AC 提交 — vjudge solution 69896828**](https://vjudge.net/solution/69896828)
完整源码包含本次新沉淀进几何模板的:
- `Point::normL1()` / `Point::normLinf()` 两个成员(曼哈顿 / 切比雪夫范数)
- `distancePP` / `distancePPL1` / `distancePPLinf` 三个自由函数(开方欧氏 / 曼哈顿 / 切比雪夫距离)
完整源码见末尾「📎 完整源码」附件 + 下方折叠块(折叠块走 raw API 单独追加,因为 30 KB 超 markdown 单段限制)。
::: 展开完整 C\+\+ 源码(含几何模板 \+ Solve,约 970 行)
```cpp
// 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"的心路——主要是**思路推导一条线下来**:
1. 看到 $\mathrm{dis1} / \mathrm{dis2}$ 直觉就反应"这跟方向有关",写成 $|\cos\theta| + |\sin\theta|$ 后就锁死"找最接近 $\pm 45^\circ$ 方向的点对"
1. 但是 $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$ 都不在凸包上
1. 直接看了官方题解才知道是**中值不等式**那一招。证明优美但"赛场上能不能想到"是另一回事——下次见到「对所有点对极大化方向相关量」类几何题先把这条工具拿出来用
1. 实现时本来要在 Solve 里手写 L1 / L2 距离,顺手沉淀进几何模板(这次加了 `distancePP` / `distancePPL1` / `distancePPLinf` 三个自由函数 + `Point::normL1` / `normLinf` 两个成员),后续题目直接复用
> **Take-away**:「最大化 / 最小化 $f(\theta_{ij})$ 」( $\theta_{ij}$ 是点对方向角)这一类问题,先想"排序 + 邻点扫"配中值不等式,比凸包 / 旋转卡壳更对路。
# 附件
下面是这道题的可交互 HTML 讲解 + 3 张关键帧截图 + 完整源码下载。
[distance_ratio.html.txt](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/e411d69d-eb70-4068-804d-c337391721a3/distance_ratio.html.txt?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB466VDFLUMJ3%2F20260515%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260515T072640Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEKb%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLXdlc3QtMiJGMEQCIFvNQULKzwWhcxPRmE4P2VkGXs1sASy2SgeIvMUMEa55AiA%2BZLQCKa9B0JTI%2F87H5k1ZBXVZrT3M0gryhswon3sfmSr%2FAwhvEAAaDDYzNzQyMzE4MzgwNSIML%2BqQrly5DiE3G1%2FEKtwD6v7l2pdZtaRF1B61h65z5gT4NKX7TWuqT0Ybd3X7g9LuhKboDMFQUHWVQF4WEoHE7t2HIyFx8uY7zKlS0ZiP7eXv8D8ayn7%2F0ctP28kgqdajqDfTBXMbYGrWBubacor%2Bo4rgE7m71D29U6khmVGX6%2FWJpgErnDqAwc9JjHCOGBFjg4uv3LeeDmXY2NtgmEIcu588yralIyiOXxa%2BCHXpb1egbIpbKb6Xf7gxKH3fkEtGOnjQFjF3F5%2FoOY6G9uMSo9fmhFgy1tf%2F3OLsJVBfkC5ZtSbuBkYQQP8XU3XsY%2BVkmaVbEBs0%2BBmRewDa7JUGgvL%2BI5aQ%2FoyVjvpeZrufDbrA%2BiokX%2BrsfIEFKWXUqyhV1BWVVXuWi9Ise0d3KeqOE5XBssWHQAUVmqA1nVLMLn7V1an2wSezC7GWcnPtuVLsUQlchK6Dbl8k7%2B2R2yN%2FE942PQROfWDwhCSLz1CZ5hbvCyqsLs2MxJ%2FMKic8zETtlgHBmRVrv04rWrOBaQNVpdnEnu%2FpdybRolUyjTmMouhdEPTp%2FlYN8YubKKPKE1QxzEa2N0e40lH9oncjX2fUdzYfUSRAYFwdAJTih4i6kO9BdI83CfY9EkIhC7t3EHWXW2v%2FgMyGLBzNUN0wtPSa0AY6pgF0AI4D2poHJCQFEgqrNu9iw1iE6DV%2F1%2FIPEyzYHrEtNuCWaV2xDgi1vjDtkAv23DE2y0jLc7BuytTTTtwK%2BQ0wvRc5ImC4QZyJvfqGQjF1Hctwhx6KclWba1lQ%2BvM7neB15j4qxW6l4gfeSwAelhWCMca7UrL4VdoV6ebiEYYopoqUxw31FaEypGyWtt6Azpya34xWXH9TtFCii%2BtqkjNa8wkT%2Bgih&X-Amz-Signature=206de62ddf80f3934e51c0f1343d7a5d76867b5e66433637149db90b648ba74e&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)


