P7918 [Kubic] Lines 题解

银杉水杉秃杉 · 2021-11-04 11:13:58 · 题解

这道题跟平行线有关，将平行的直线划为一组进行讨论，相当于把平行线合并成一条直线。

合并后所有直线互不平行，任意去掉一组平行线也能满组覆盖到所有交点。要使得剩下的直线数量最小，所以答案为 ans= 直线总数量 n - 数量最多的一组平行线的数量。

用直线的斜率来区分不平行的直线，斜率相同的两条直线互为平行线。

注意：由于用斜率记录直线，double 的精度可能会不够，所以要用上 long double。

很多人用的是 map 来记录平行线。事实上也可以不用 map，将斜率进行排序，数一数重复的数量，找出最大值即可。

两种写法我都放出来给大家看看：

有 map 版：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 0x3f3f3f3f;
int n, m, mx;
map<long double, int> s;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        long double f = (a == 0) ? inf : (long double)b / a; //当a=0时，斜率为正无穷
        if (++s[f] > mx)
            mx = s[f];
    }
    printf("%d\n", n - mx);
    return 0;
}

无 map 版：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 0x3f3f3f3f;
int n, m, mx, s[N];
long double f[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        f[i] = (a == 0) ? inf : (long double)b / a; //当a=0时，斜率为无穷
    }
    sort(f + 1, f + n + 1);
    s[++m] = 1;
    for (int i = 2; i <= n; i++) //数重复的
        if (f[i] == f[i - 1])
            s[m]++;
        else
            s[++m] = 1;
    for (int i = 1; i <= m; i++) //找最大值
        if (s[i] > mx)
            mx = s[i];
    printf("%d\n", n - mx);
    return 0;
}

感谢 @y1z1 大佬提供的 hack 数据。（原先写的 double，后来改成 long double 了）