Gym 105173 M - House

题目大意

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