Znzryb's Blog
0%

Posted on Edited on

题目大意

CF gym 105231 I - Neuvillette Circling | rating 2100 | 2024 (ICPC) 江西省赛 武大 WHU 命题组 | n≤100n \le 100 ，时限 2 秒

给 NN 个宝藏在平面上 (xi,yi)(x_i, y_i) ，任意两个宝藏之间有一条线段（路径），每条路径上有一个丘丘人——它可能出现在线段上的任意一点（位置对抗性）。Neuvillette 画一个圆（圆心任选、半径要最小），圆上或圆内的丘丘人被秒。

要求：无论这些丘丘人具体站在各自线段的哪个位置，他都能至少干掉 mm 个。对 m=1,2,…,(n2)m = 1, 2, \dots, \binom{n}{2} 分别输出最小半径。

数据范围

  • 2≤n≤1002 \le n \le 100

  • −103≤xi,yi≤103-10^3 \le x_i, y_i \le 10^3 ，坐标全是整数

  • 保证无两点重合 / 无三点共线

  • 答案精度 10−610^{-6}

样例 ( n=5n = 5 )

输入：

1
2
3
4
5
6
5
-6 -9
2 4
9 2
1 -1
-4 -5

输出（10 行）：

1
2
3
4
5
6
7
8
9
10
2.23606798
4.28602124
4.28602124
7.38241153
7.38241153
7.38241153
9.30053762
9.30053762
9.30053762
9.30053762

思路讲解

一句话

对抗性建模 →\to 「包住整段」等价于「包住两端点」（圆盘是凸集） →\to 圆里有 kk 个原始点就保证 (k2)\binom{k}{2} 条边的丘丘人都被秒 →\to 题目变成 对每个 kk 求最小 kk 点覆盖圆。MEC 定理给出候选圆只有 O(n3)O(n^3) 个：两点直径 + 三点外接。总复杂度 O(n4)O(n^4) ， n=100n = 100 下宽松到不用卡常。

Step 1：对抗性建模——把「覆盖一条边」翻译成「包住两个点」

题目说丘丘人可能出现在线段任意一点，又要求无论它在哪都得能杀掉。这是经典对抗设定：玩家先确定圆，丘丘人才挑位置。

「保证这条边上的丘丘人被秒」 ⟺\Longleftrightarrow 「整条线段在圆盘内」

否则对手把丘丘人放在圆外那一点。

再用「圆盘是凸集」收一刀——圆盘内任意两点的连线段仍在圆盘内：

整条线段在圆盘内 ⟺\Longleftrightarrow 线段两端点都在圆盘内

这一步把「覆盖一条边」降级为「包住它的两个端点」，几何复杂度直接塌一档。

Step 2：从覆盖边到覆盖点—— (k2)\binom{k}{2} 平台结构

承接上一步。如果圆盘里有 kk 个原始点，这 kk 个点两两之间共 (k2)\binom{k}{2} 条边、其两端点都在圆内 ⇒\Rightarrow 这 (k2)\binom{k}{2} 条边上的丘丘人全保证被秒。

所以题目等价为：

对每个 k=2,3,…,nk = 2, 3, \dots, n ，求「至少包住 kk 个原始点的最小圆」的半径 ansk[k]\mathrm{ans}_k[k] 。

输出时，给定 mm 找最小的 kmk_m 满足 (km2)≥m\binom{k_m}{2} \ge m ，那个槽的最小半径就是答案。代码里更优雅的写法：把每个候选圆按 (in_cir_cnt2)\binom{\text{in\_cir\_cnt}}{2} 直接落到 mn_rad[ans] 槽，最后做一遍 suffix-min 把「更大 mm 的最优半径」向左 propagate 到小 mm 上——殊途同归，省一步反查。

样例的 4 个圆刚好对应 k=2,3,4,5k = 2, 3, 4, 5 四个平台：

| kk | 圆 | 半径 ( ansk[k]\mathrm{ans}_k[k] ) | 管的 mm |

| — | — | — | — |

| 2 | 紫（最近对直径） | 2.236 | 1 |

| 3 | 红（3 点外接） | 4.286 | 2, 3 |

| 4 | 蓝（4 点 MEC） | 7.382 | 4, 5, 6 |

| 5 | 绿（全 5 点 MEC） | 9.301 | 7, 8, 9, 10 |

每个 kk 管 (k2)−(k−12)=k−1\binom{k}{2} - \binom{k-1}{2} = k - 1 个 mm ，正是三角形数 1, 2, 3, 4, ……

Step 3：MEC 定理迁移——候选圆只有 O(n3)O(n^3) 个

MEC（minimum enclosing circle）的关键结构性事实：

MEC 定理： nn 个点的 MEC ，边界圆周上恰好经过 2 或 3 个原始点。

这是 Welzl 随机增量算法的依据。

  • 「至少 2」：反证。如果边界上 0 或 1 个原始点，可以把圆心稍微挪一挪 ++ 半径稍减，所有包含点继续在内 ⇒\Rightarrow 半径更小，矛盾。

  • 「至多 3」：平面上不共线 3 点决定唯一外接圆，题面保证「无三点共线」就是为了避开退化。

关键迁移：本题最优圆 R∗R^* （最小 kk 点覆盖圆）也满足这条结构性质——同样的 shrink/move 论证：若 R∗R^* 边界 b≤1b \le 1 个原始点，可以缩小并保持「含 ≥k\ge k 个点」不变 ⇒\Rightarrow 与最优矛盾。所以 R∗R^* 必定是某个 ∣S∣≥k|S| \ge k 的子集的 MEC，由 2 或 3 个原始点决定。

这一刀把「枚举对象」从点的子集翻转成了圆。

候选圆集合：

  • (n2)\binom{n}{2} 个 两点直径圆（任选两点作直径）

  • (n3)\binom{n}{3} 个 三点外接圆（任选三点的 circumcircle）

规模 O(n3)O(n^3) ，对每个圆 O(n)O(n) 数它包了多少个原始点 →\to 总 O(n4)O(n^4) 。

Step 4：复杂度算账

n=100n = 100 时：

(1002)+(1003)=4 950+161 700≈1.67×105 候选圆\binom{100}{2} + \binom{100}{3} = 4\,950 + 161\,700 \approx 1.67 \times 10^5 \text{ 候选圆}

每圆 ×100\times 100 次数点 →\to 约 1.67×1071.67 \times 10^7 次基本运算。2 秒时限内相当宽松，连卡常都不需要。

Step 5：FP 精度坑——这题的 WA 点

枚举候选圆时，圆的 2 或 3 个定义点本应在边界上（数学上 ∣p−c∣2=r2|p - c|^2 = r^2 恰好相等）。但 circle_from_diameter / outcircle_triangle 算出来的 r = sqrt(d) / 2 后，squared(r) = r * r 经过 sqrt 一来再 square 一回的 round trip，得到的不再是精确的 d/4d/4 ，会有 ULP 级误差：

1
2
3
4
5
d  =  5: r*r = 1.2500000000000002,  d/4 = 1.25
d  = 13: r*r = 3.2499999999999996,  d/4 = 3.25   ← r*r < d/4，边界被判到圆外
d  = 20: r*r = 5.000000000000001,   d/4 = 5.0
d  = 50: r*r = 12.500000000000002,  d/4 = 12.5
d  =113: r*r = 28.250000000000004,  d/4 = 28.25

如果用 dist² <= r² 严格比较，当 r² 偶尔比真值小时，定义点被判到圆外（dist² > r²），漏算 →\to in_cir_cnt 不对 →\to mn_rad[m] 拿不到本该的候选半径 →\to WA。

样例 d=20d = 20 那个紫圆恰好走在 +ε+\varepsilon 一侧（<= 成立、定义点被算入），样例侥幸过；但测试数据里只要撞一个 d=13d = 13 这类形状，定义这个 diameter circle 的 2 个原点就漏算，整个候选圆失效。

修法：用 sgn(dist² - r²) <= 0 容差判定。

1
2
3
4
5
// AC https://vjudge.net/solution/69993234 使用 sgn 避免精度问题
template<class U>
bool is_point_in_circle(const Point<U> &p) {
    return sgn(distancePPNorm(p, c) - squared(r)) <= 0;
}

sgn 把 ∣x∣<ε|x| < \varepsilon 当作 0，吸收 sqrt →\to square 的 ULP 抖动。这个 patch 顺手同步到了 ICPC 几何模板 + espanso :Circle snippet，以后展开就自带正确版。

📎 动画与源码

完整带教对话录 PDF（mentor.tex 编译产物，含 6 步推导 + 我画的 4 个圆草图 + 全过程问答）在末尾附件区，可下载查看。

AC 代码

AC 提交链接（vjudge / Gym-105231I）

核心 Solve() 函数：枚举 (n3)\binom{n}{3} 个外接圆 + (n2)\binom{n}{2} 个直径圆，每个圆 O(n)O(n) 数包含点数，按 (in_cir_cnt2)\binom{\text{in\_cir\_cnt}}{2} 落到 mn_rad 槽，最后 suffix-min 把大 mm 的最优半径向左 propagate。

心路历程（WA → AC）

  • 第一次提交：大数据 WA，样例 AC。算法骨架完全对，suffix-min 也对，输入输出格式也对。

  • 卡点诊断思路：「样例 AC + 大数据 WA + 几何题」三联立基本就是 FP 精度在 boundary 上吞 byte。

  • 定位到 is_point_in_circle 的 dist² <= r² 严格比较——r = sqrt(d)/2 再 squared(r) 跑了一趟 sqrt → square 的 round trip，对 ll 整数输入精度只够覆盖大约半数 dd 值。

  • 样例 d=20d = 20 那个紫圆（直径 (−6,−9)↔(−4,−5)(-6,-9) \leftrightarrow (-4,-5) ）正好走在 +ε+\varepsilon 一侧，所以样例没暴露这个 bug；测试数据撞 d=13d = 13 类形状才漏算。

  • 修法：return sgn(distancePPNorm(p, c) - squared(r)) <= 0; 把硬比较改成 sgn 容差判定，一行改完 AC。

  • 顺便把这个 patch 同步到 ICPC 几何模板 的 Circle struct + espanso :Circle snippet，以后再做几何题展开模板就自带正确版，省一次踩同一个坑。

附件

完整带教对话录（mentor.tex 编译产物 PDF，含 6 步推导）+ AC C++ 源码（.cpp.txt）直接附在下方，可下载查看。

完整带教对话录（mentor.tex 编译产物，6 步推导 + 第 1 步用户手画 4 个圆草图 + 全过程问答 + WA 诊断）

Neuvillette_Circling.cpp.txt

Posted on

题目大意

洛谷 P5939 [POI 1998 R3] 折线

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

数据范围

1≤n≤300001 \le n \le 30000 ， 0≤xi,yi≤300000 \le x_i, y_i \le 30000 。时限按常规 1s 算，目标复杂度 O(nlog⁡n)O(n\log n) 。

样例

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

思路讲解

一句话

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

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

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

∣y2−y1∣≤x2−x1|y_2 - y_1| \le x_2 - x_1

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

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

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

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

y2−y1≤x2−x1且y1−y2≤x2−x1y_2 - y_1 \le x_2 - x_1 \quad\text{且}\quad y_1 - y_2 \le x_2 - x_1

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

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

条件就清爽成了 uP≤uQu_P \le u_Q 且 vP≤vQv_P \le v_Q 。

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

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

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

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

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

第四步：Dilworth / 导弹拦截

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

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

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

📎 动画与源码

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

AC 代码

AC 提交（vjudge）

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

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

  • Dilworth 方向写反：第一版写成 LIS(uv, false) ——求的是 vv 的 最长非降子序列 ，量根本不对。它和"最小链覆盖"没关系，只是在样例 1 上巧合都等于 3，没暴露。

  • 照出 bug 的反例：输入 2 / 0 0 / 2 0 。两点 (0,0),(2,0)(0,0),(2,0) 在同一条水平折线上（夹角 0∘0^\circ ），正解 = 1 ；错误代码： (u,v)=(0,0),(2,2)(u,v)=(0,0),(2,2) ， vv 序列 [0,2][0,2] ，最长非降 = 2 → 输出 2 ，错。

  • 修法：改成求 vv 的最长严格下降子序列——uv[i] = -uvA[i].y; 取负后 LIS(uv, true); （strict 走 lower_bound ），等价于求最长严格下降。一发 AC。

  • 沉淀的易错点：(1) Dilworth 是"最少非降覆盖 = 最长 严格下降 “，方向 / 严格性都不能错；(2) 支配条件是"不下降"含等号，不是"严格上升”，同 uu / 同 vv / 重点都得能进同一条链；(3) 排序并列方向（同 uu 按 vv 升）要和"求严格下降"配套，弄反会把可同链的点错算成反链。

附件

下面附件均已直接传入本页面，可在 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

Posted on

题目大意

洛谷 P1742 最小圆覆盖：给 NN 个平面点（N≤105N\le 10^5，坐标实数），求一个半径最小、且能把所有点都包住（含边界）的圆，第一行输出半径、第二行输出圆心坐标，精度 10−910^{-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)O(N)。这道题真正的坑不在算法本身，在内层 for j / for k 必须升序——内层判定下标改对了、循环方向写反，照样直接 WA。

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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（本题关键）

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

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

  • **同样例 6 点实测：**升序连跑 30/30 全 = r=5r{=}5、圆心 (5,5)。

  • 倒序飘忽：r=5r{=}5（对） / r=6.23r{=}6.23 圆心 (5,9.375)（盖住但非最小 = WA） / r=3.876r{=}3.876 圆心 (7.05,5.35)（连 (1,2) 都没盖 = 非法解）。

  • **两种坏法：**漏点（已扫点被甩出 → 非法），或后续 circle_from_diameter 重置把圆撑大（非最小）。

机制图：以 j=3 重建为例。升序「已扫」=「引理担保前缀」两段重合（归纳闭合）；倒序引理只担保前缀 p0..p2，实际已扫的却是后缀 p4..p6，错位 → 不变量断裂。

几何后果：绿实线 = 正解最小圆 (5,5) r=5；红虚线 = 倒序某次实际跑出的圆 (7.05,5.35) r=3.876，(1,2) 和 (4.5,1) 都被甩在圈外 → 非法解。

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

step 0 — L0 起手：res = 单点 p0（蓝实线 r=0）；绿虚线 = 真最小圆 r=5 参照物；右栏阶段 L0。

中间帧 — L2：钉 p_i,p_j 后扫 p_k 算外接圆；右栏实时列「引理担保前缀」vs「实际已扫」+ 重合/错位 verdict。

末帧 — 升序跑完：蓝圈收敛到绿圈，r=5 正解 ✓。切「倒序」按钮重跑会停在错的圆（非最小 / 漏点）。

📎 动画与源码

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

AC 代码

AC 提交链接：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

Posted on

题目大意

比赛：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

题面

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

  • ABCDABCD 是一个矩形（按顺序，即 AB∥CDAB \parallel CD 、 AD∥BCAD \parallel BC 、 AD⊥ABAD \perp AB ）

  • CDECDE 是以 CDCD 为底的等腰三角形（ ∣CE∣=∣DE∣|CE| = |DE| ）

  • EE 在 CDCD 直线远离 ABAB 那一侧（数学条件： DA→⋅DE→<0\overrightarrow{DA} \cdot \overrightarrow{DE} < 0 ）

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

数据范围

  • 5≤n≤3005 \le n \le 300

  • ∣xi∣,∣yi∣≤109|x_i|, |y_i| \le 10^9 （整数坐标）

样例

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

思路讲解

一句话

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

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

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

  • AA 必须满足 AD⊥CDAD \perp CD 且 B=A+(C−D)B = A + (C - D) 也在点集 —— AA 完全由"在过 DD 的垂线上 + BB 是否凑得齐"决定，跟 EE 无关

  • EE 必须满足 ∣CE∣=∣DE∣|CE| = |DE| ，即 EE 在 CDCD 的中垂线上 —— 跟 AA 也无关

  • 唯一耦合的条件是" AA 和 EE 在 CDCD 异侧"

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

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

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

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

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

判定 条件 归类
PP 能当 AA 吗？ (P−D)⋅(C−D)=0(P - D) \cdot (C - D) = 0 且 P+(C−D)P + (C - D) 也在点集 按 cross(C−D,P−D)\mathrm{cross}(C - D, P - D) 符号 → ALA_L / ARA_R
PP 能当 EE 吗？ $\ P - C\ ^2 = \ P - D\ ^2$ （在 CDCD 中垂线上） 按同一 cross 符号 → ELE_L / ERE_R

这一对 (C,D)(C, D) 的贡献是 AL⋅ER+AR⋅ELA_L \cdot E_R + A_R \cdot E_L ——把 AA 和 EE 强行配到 CDCD 两侧。

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

Step 8: 固定 (C,D) = ((4,2), (0,2))。绿色虚线 = A/B 必在过 C/D 的两条垂线上；紫色虚线 = E 必在 CD 中垂线上。

AA 候选的两条轨迹 + EE 候选的一条轨迹

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

  • 绿色虚线（两条）：过 C,DC, D 各画一条 ⊥CD\perp CD 的垂线 —— AA 必在过 DD 那条上， BB 必在过 CC 那条上

  • 紫色虚线（一条）： CDCD 的中垂线 —— EE 必在它上面

  • 按每个候选点落在 CDCD 哪一侧（cross 的符号）分到 LL / RR 桶里

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

Step 14: 汇总。A_L=0, A_R=1 (P=(0,0) 配出 B=(4,0)), E_L=1 (P=(2,4)), E_R=1 (P=(2,0))。贡献 = A_L·E_R + A_R·E_L = 0+1 = 1。

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

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

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

复杂度 + 溢出注意

  • 复杂度： O(n2)O(n^2) 对 ×\times O(n)O(n) 扫点 =O(n3)= O(n^3) 。 n=300n = 300 时约 2.7×1072.7 \times 10^7 次基本操作，常数小，稳过

  • 点集查询用 unordered_map<pair<ll,ll>, int> 或先排序后二分都行（cpp 走的是 sort + binary_search）

  • 溢出：坐标到 10910^9 。判 EE 的 ∣P−C∣2−∣P−D∣2=−(C−D)⋅(2P−C−D)|P - C|^2 - |P - D|^2 = -(C - D) \cdot (2P - C - D) 展开后内部乘积量级 4×10184 \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）：

心路历程

  • 5 个点同时枚举想都别想： O(n5)=2.4×1012O(n^5) = 2.4 \times 10^{12} ，肯定要解耦。题目让 (A,B,C,D,E)(A, B, C, D, E) 5 个点中 C,DC, D 同时是矩形的边和三角形的底 → 自然以 C,DC, D 为主角， A,B,EA, B, E 都跟着定下来

  • BB 是被 AA 顺便确定的：注意 B−A=C−DB - A = C - D （矩形对边等长平行），所以扫到一个 AA 候选时立刻知道 BB 应该在哪，查一次点集即可 —— 不用单独枚举 BB

  • 异侧条件靠 cross 符号实现：题面给 DA→⋅DE→<0\overrightarrow{DA} \cdot \overrightarrow{DE} < 0 看起来是浮点不等式，但本质就是 " A,EA, E 在 CDCD 直线两侧"，等价于 cross(C−D,P−D)\mathrm{cross}(C - D, P - D) 异号 —— 整数判完美

  • 有序对 vs 无序对：第一次写很容易写成有序对枚举然后忘了 ÷2\div 2 ，或者无序对枚举但只算 AL⋅ERA_L \cdot E_R 漏数一半。核心是想清楚 {c,d}\{c, d\} 作为无序对枚举一次后， ALER+ARELA_L E_R + A_R E_L 已经覆盖了 AA 在两侧 × EE 在异侧的全部 4 种 (label, side) 组合，等价于有序对求和后 ÷2\div 2

  • 溢出 __int128：坐标 10910^9 平方 101810^{18} 还在 long long 内，但两个平方相减 / 相加到 4×10184 \times 10^{18} 就溢了。模板里 cross / dot / Point::norm() 整数路径下自动走 __int128，所以直接调 distancePPNorm 比较两个 __int128 就行，不用手动加 (__int128) 强转

  • 点集查询用 sort + binary_search： n≤300n \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

Posted on

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

题目大意

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

AB→⋅AC→=(xB−xA)(xC−xA)+(yB−yA)(yC−yA)\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

1
2
3
4
5
6
5
0 2
0 -2
3 0
-3 0
0 -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，把点积写成投影形式：

AB→⋅AC→=∣AB→∣⋅projAB→(AC→)\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∈H  AB→⋅AC→=arg⁡min⁡C∈H  ∣AB→∣⋅projAB→(AC→)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 点，本会话抓到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
17
16 100
104 -9
-18 94
-86 45
-87 -47
54 89
-30 -94
-60 -78
52 -90
2 -103
-98 9
-97 -14
96 -36
74 67
-61 83
96 31
65 -72

真最优：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。

正确修法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 找 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 个改动：

  1. bStart = (aPos + 1) % H：让 b 从真正的 CCW 起点开始

  2. bCnt = H - 1：走 h-1 步绕回 A_prev 终止（A 自己天然跳过）

  3. 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()：

心路历程（WA → AC）

按真实的 debug 过程列：

  1. 第一版按题解写：枚举 A、b 沿 hull 走 h 步、c 双指针。样例 1 过，WA on test 44。

  2. 加 if (A.id == convex[b].id) continue; 跳过 b = A 退化轮。样例 1 仍过，仍 WA on test 44。

  3. cyaron 风格 stress test：本机 gen 17~30 点全在 hull 上的随机数据（椭圆采点 + 强制 h ≥ 5）+ brute O(n³) 对拍。第 204 次种子抓到 17 点反例。

  4. 手算反例确认根因：A = p11 在 hull[1]（不是 hull[0]！），b 按 hull 顺序走方向不单调（+92.5° → -73° 回退 165°），c 单向推进跟不上。

  5. 正确修法：b 起点改 (aPos + 1) % H、走 H-1 步；c 初始扫描以 convex[bStart] 为 b 基准（不再用 convex[0]）；check 改 >=。

  6. 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 退化分支撒不重点）。

附件

demo 关键帧 1: 初始状态, 5 个点全识别, 凸包未建

demo 关键帧 2: step 8, A=p1 在 hull 顶点, B=h0=p3, C*=h2=p2, 当前 dot=-5, 历史最小 -5

demo 关键帧 3: 算法完成, 历史最小收敛到 -8 (最优 A=p4 内部点, B=p2, C=p3)

astral_decay_demo.html.zip

Astral_Decay.cpp.txt

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