自动搬运

查看原文

来自洛谷，原作者为

	Origin0107 never give up

搬运于2025-08-24 22:34:17，当前版本为作者最后更新于2021-11-03 20:34:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update on 11.12:将 double 换为 long double 减小精度造成的误差，感谢

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;
}