4838367_wa.cpp

部分PKU上的源码

#include<iostream>
#define key 99983
using namespace std;
struct ve
{
	int x,y;
	int num;
}q[400010];
int ql;
int hash[100000];
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 getkey(int x,int y)
{
	int re=x*y;
	re%=key;
	if(re<0) re+=key;
	return re;
}
int main()
{
	cin>>n;
	int i,j,best;
	ql=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;}
			int p=getkey(tx,ty);
			while(hash[p])
			{
				if(q[hash[p]].x==tx&&q[hash[p]].y==ty) 
				{
					q[hash[p]].num++;
					if(q[hash[p]].num>best) best=q[hash[p]].num;
					find=true;
				}
				p++;
			}
			if(!find)
			{
				hash[p]=ql;q[ql].x=tx;q[ql].y=ty;q[ql].num=0;ql++;
			}
		}
	}
	best++;
	best/=2;
	cout<<best<<endl;
	return 0;
}