Line连线游戏 bzoj-1610 Usaco-2008 Feb

题目大意:Farmer John最近发明了一个游戏,来考验自命不凡的贝茜。游戏开始的时 候,FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板,其中第i个点 的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000; -1,000 <= Y_i <= 1,000)。 贝茜可以选两个点画一条过它们的直线,当且仅当平面上不存在与画出直线 平行的直线。游戏结束时贝茜的得分,就是她画出的直线的总条数。为了在游戏 中胜出,贝茜找到了你,希望你帮她计算一下最大可能得分。

想法:因为一个木板可以使用多次,所以我们暴力枚举任意两个点,并用一个STL将这个斜率存起来,我这里用两个数组,记录分子和分母以免重复,然后sort后扫一遍。

最后,附上丑陋的代码... ...

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 220 
using namespace std;
struct Node{int u,d;}f[N*N]; int x[N],y[N],ans,tot;
inline bool cmp(Node a,Node b){return a.u==b.u?a.d<b.d:a.u<b.u;}
// int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
	int n; cin >> n ;
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	bool flag=false;
	// puts("***");
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
	{
		int p=x[i]-x[j],q=y[i]-y[j];
		if(q==0)
		{
			if(!flag) ans++,flag=true;
			continue;
		}
		// puts("Bitch");
		// printf("%d %d\n",i,j);
		int g=__gcd(p,q);
		f[++tot].u=p/g,f[tot].d=q/g;
	}
	// puts("***");
	sort(f+1,f+tot+1,cmp);
	// puts("***");
	for(int i=1;i<=tot;i++)
	{
		if(f[i].u==f[i-1].u&&f[i].d==f[i-1].d) continue;
		// printf("Woc %d %d\n",f[i].u,f[i].d);
		ans++;
	}
	// puts("***");
	printf("%d\n",ans);
	return 0;
}
/*
4
-1 1
-2 0
0 0
1 1
*/

 

 小结:刷水真开心...