4838938_re.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int k[2105][2105];
int x[250];
int y[250];
int n;
int getgong(int x,int y)
{
	int temp;
	if(y>x) 
	{
		temp=x;
		x=y;
		y=temp;
	}
	while(x%y)
	{
		int t=x%y;
		x=y;y=t;
	}
	return y;
}
int main()
{
	cin>>n;
	int i,j,best;
	best=1;
	for(i=0;i<n;i++) 
	{
		cin>>x[i]>>y[i];
		for(j=0;j<i;j++)
		{
			int tx,ty,gong;
			bool find=false;
			tx=x[i]-x[j];
			ty=y[i]-y[j];
			gong=getgong(tx,ty);
			tx/=gong;
			ty/=gong;
			if(tx<0){tx*=-1;ty*=-1;}
			k[tx+1050][ty+1050]++;
			if(k[tx+1050][ty+1050]>best) best=k[tx+1050][ty+1050];
		}
	}
	best*=2;
	for(i=1;i*i<best;i++) {}
	cout<<i<<endl;
	return 0;
}