【USACO 2008 FEB】连线游戏 Game of Lines

【题目】

传送门

题目描述：

Farmer John 最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ 会给贝茜一块画着 $n$n（$2≤n≤200$2≤n≤200）个不重合的点的木板，其中第 $i$i 个点的横、纵坐标分别为 $x_i$xi​ 和 $y_i$yi​（$-1000≤x_i≤1000$−1000≤xi​≤1000；$-1000≤y_i≤1000$−1000≤yi​≤1000）。

贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

输入格式：

第 $1$1 行：输入 $1$1 个正整数 $n$n 。
第 $2\dots n+1$2…n+1 行：第 $i+1$i+1 行用 $2$2 个用空格隔开的整数 $x_i$xi​，$y_i$yi​ ，描述了点 $i$i 的坐标。

输出格式：

输出 $1$1 个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数 。

样例数据：

输入
4
-1 1
-2 0
0 0
1 1

输出
4

备注：

【输出说明】

贝茜能画出以下 $4$4 种斜率的直线：$-1$−1，$0$0，$1/3$1/3 以及 $1$1 。

【分析】

一道比较简单的题。

我们实际上就是要求出最多有多少条直线互不平行。

由于 $n$n 比较小，我们可以枚举所有的点对，把所有的斜率都统计出来，排序后去重即可。

最后注意一下精度问题就可以 A 掉这道题了。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 205
#define eps 1e-8
using namespace std;
double Slope[N*N];
struct point{double x,y;}p[N];
int main()
{
	int n,i,j;
	scanf("%d",&n);
	int ans=0,tot=0;
	for(i=1;i<=n;++i)
	{
		scanf("%lf%lf",&p[i].x,&p[i].y);
		for(j=1;j<i;++j)  Slope[++tot]=(p[i].y-p[j].y)/(p[i].x-p[j].x);
	}
	sort(Slope+1,Slope+tot+1);
	Slope[0]=-10000;
	for(i=1;i<=tot;++i)
	  if(Slope[i]-Slope[i-1]>eps)
	    ans++;
	printf("%d",ans);
	return 0;
}