给定 \(n\) 条解析式为 \(ax+by+c=0\) 的直线,选出最少的直线去覆盖所有交点。
显然,没有删掉的直线一定是互相平行的,否则一定有至少一个交点没有被删掉。
所以其实就是要选出最多的直线使它们两两平行。
对于每一条直线暴力找出有多少条直线与它平行,取最大值即可。
用 unordered_map
维护,时间复杂度 \(\mathcal O(n \log n)\)。
#include <bits/stdc++.h> using namespace std; #define int long long inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int n; int a[100007], b[100007], c; map<pair<int, int>, int> mp; int ans; int A, B; signed main() { n = read(); for (int i = 1; i <= n; ++i) { a[i] = read(), b[i] = read(), c = read(); mp[make_pair(a[i], b[i])]++; if (a[i] == 0) A++; if (b[i] == 0) B++; } if (A + B == n) { cout << min(A, B) << "\n"; return 0; } for (int i = 1; i <= n; ++i) ans = max(ans, mp[make_pair(a[i], b[i])]); cout << n - ans << "\n"; return 0; }