3129703_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <map>
#include <algorithm>

using namespace std;

int x[701], y[701];
typedef pair <int,int> type;
map <type , int> h;

int gcd(int a,int b)
{
	return a==0?b:gcd(b%a,a);
}

int main()
{
	int i, j, n;
	int a, b;
	int max, ans;

	while(scanf("%d",&n)==1,n)
	{
		for(i = 0; i < n; i++)
		{
			scanf("%d%d",&x[i],&y[i]);
		}
		ans = 0;
		for(i = 0; i < n; i++)
		{
			h.clear();
			int tmp = 0;
			max = 0;
			for(j = 0; j < n; j++)
			{
				if(x[i]==x[j]&&y[i]==y[j])
				{
					tmp++;
					continue;
				}
				b = y[j]-y[i];
				a = x[j]-x[i];
				if(a < 0)
				{
					a *= -1;
					b *= -1;
				}
				int g = gcd(a,b>0?b:-b);
				type p = make_pair(a/g,b/g);
				h[p]++;
				if(h[p] > max)
				{
					max = h[p];
				}
			}
			max += tmp;
			if(max>ans)
			{
				ans = max;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}