正经题解｜画板

提示1

至少需要几条直线可以构成一个封闭图形？

提示2

如果存在一组平行线和另一组斜率不同的平行线会是什么情况？

题目解析

提示1：最少 $3$ 条斜率不同且没有相交于同一点的直线可以构成一个封闭图形。
提示2：如果存在一组平行线和另一组斜率不同的平行线，那么必然可以构成一个封闭图形。

根据 提示2 我们将题目分成两种情况。

A. 存在一组平行线和另一组斜率不同的平行线。
B. 不存在一组平行线和另一组斜率不同的平行线。

对于 情况A，我们可以将所有斜率相同的直线的截距 $b$ 放到一个集合中，令斜率为 $k_i$ 但截距不同的直线数量为 $cnt_{k_i}$。
若存在 $cnt_{k_i} > 1, cnt_{k_j} > 1(k_i \neq k_j)$ 则必然存在封闭区域。

对于 情况B，此时所有的直线中至多有一个斜率 $k_i$ 中截距不同的直线数量 $cnt_{k_i} > 1$， 对于其他斜率 $cnt_{k_j} = 1, (k_j \neq k_i)$。

那么对于 情况B 我们只需要考虑 提示1 的情况：$3$ 条斜率不同且没有相交于同一点的直线可以构成一个封闭图形即可。

对此我们可以枚举直线 $i$，然后枚举直线 $j, (k_i \neq k_j)$，若存在两条直线 $j_a, j_b (k_{j_a} \neq k_{j_b})$ 和直线 $i$ 相交与不同的两点，则说明可以构成封闭图形。

在实现上，情况B 留给我们的特殊性质，使得我们可以通过枚举斜率 $k_i$ 的方式得到更低的复杂度（思考下为什么）。

AC代码

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

constexpr double EPS = 1e-8;

int check() {
    int n; cin >> n;
    map<int, set<int>> lines;
    for (int i = 0; i < n; ++i) {
        int k, b;
        cin >> k >> b;
        lines[k].insert(b);
    }
    // 斜率不同的平行线对应斜率数量统计
    int same_slope_cnt = 0;
    for (auto &[k, seq] : lines)
        if (seq.size() > 1)
            ++same_slope_cnt;
    // 超过一个斜率有一组平行线，满足情况A返回true
    if (same_slope_cnt > 1) return true;
    // 情况B：枚举斜率
    for (auto &[k1, seq2] : lines) {
        for (auto &b1 : seq2) {
            // 设置交点为无穷大
            double x1 = 1e9, y1 = 1e9;
            // 统计不同交点数量
            int cnt = 0;
            for (auto &[k2, seq2] : lines) {
                if (k2 == k1) continue;
                // 最多只有一个斜率有超过一条直线，只取第一个即可
                auto b2 = *begin(seq2);
                // 计算交点
                double x2 = 1.0 * (b2 - b1) / (k1 - k2);
                double y2 = k1 * x2 + b1;
                if (abs(x1 - x2) + abs(y1 - y2) > EPS) {
                    x1 = x2;
                    y1 = y2;
                    // 存在两个不同交点，构成封闭图形
                    if (++cnt >= 2)
                        return true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--)
        cout << (check() ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

对斜率相同的直线集合去重时间复杂度为 $O(\left|k\right|\log{\left|b\right|})$。
若为 情况A，此时便可直接得到答案。
若为 情况B，枚举直线时间复杂度为 $O(n^2)$，枚举斜率的时间复杂度为 $O(n \cdot \left|k\right|)$（思考下为什么）。