4838874_re.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 52 行

#include<iostream>
#include<math.h>
#define key 99983
using namespace std;
int k[2005][2005];
int x[210];
int y[210];
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+1005][ty+1005]++;
			if(k[tx+1005][ty+1005]>best) best=k[tx+1005][ty+1005];
		}
	}
	best*=2;
	double a=(double)best;
	int b=(int)sqrt(a);
	cout<<b+1<<endl;
	return 0;
}