1118 Lining Up

問題概要

座標平面上の点がn個与えられる。
一直線上に乗る最大の点の数を求めよ。

n＜700,点の座標は全て整数とする。

解法

点iを決める。
点iと点jを結んだ傾きと点i点kを結んだ傾きが一致すれば、三点i,j,kは同一直線上にある。

したがって点iから、傾きαを作る点の数をcnt[α]などと連想配列にして数えれば、
その最大値が点iから引いた直線が、同時に乗せる点の最大数である。

これを全てのiについて動かす。
また、STLのmapを使うと遅くてダメなので、適当にハッシュなどを作る。

ソースコード

const int sz=2003;
int v[sz]; pair<int,int> ky[sz];
void hClr(){
	rep(i,sz)ky[i]=mp(-1,-1),v[i]=0;
}
int inc(pair<int,int> key){
	int h=(key.first*29+key.second)%sz; if(h<0)h+=sz;
	for(;ky[h]!=mp(-1,-1);h=(h+1)%sz)if(ky[h]==key)break;
	ky[h]=key; return ++v[h];
}

int main(){
	int n,x[700],y[700];
	while(scanf("%d",&n),n){
		rep(i,n)scanf("%d%d",x+i,y+i);
		
		int ans=min(n,2);
		rep(i,n){
			hClr(); int mx=0;
			rep(j,n)if(i!=j){
				int dx=x[j]-x[i],dy=y[j]-y[i],g=dx&&dy?__gcd(dx,dy):dx+dy;
				dx/=g; dy/=g; if(dx<0)dx*=-1,dy*=-1;
				mx=max(mx,inc(mp(dx,dy)));
			}
			ans=max(ans,mx+1);
		}
		printf("%d\n",ans);
	}
	return 0;
}