题解 P7918 [Kubic] Lines

Origin0107 · 2021-11-03 20:34:10 · 题解

update on 11.12:将 double 换为 long double 减小精度造成的误差，感谢 @yzy1 指出错误。

Problem

给定 n 条直线，选取一些直线，覆盖所有点，并输出最小值。

Solution

1. 易证 n 条直线两两相交时，需要 n-1 条直线去覆盖。
2. 当有 i 条直线相互平行时，这 i 条直线可以视作 1 条直线

记 x 为斜率相等直线数（即同一条直线的平行直线数）的最大值，答案为 n-x

Code

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

map<long double,int> m;
long double a,b,c;
int x,n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        m[b/a]++;
        x=max(x,m[b/a]);
    }
    cout<<n-x<<endl;
    return 0;
}