1118liningup.cpp

算法编程题,北京大学OnlineJudge 1118LiningUp

#include<stdio.h>  
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;


//寻找经过点最多的直线.
//枚举一个点,按斜率排序(或hash)

const int MAXN=1003;

struct Node{
	int a,b;
	int cnt;
} hs[MAXN+1];


int n;
int px[700];
int py[700];
int ans;

bool Input(){
	scanf("%d",&n);
	if(!n) return 0;
	int i;
	for(i=0;i<n;i++){
		scanf("%d%d",&px[i],&py[i]);
	}
	return 1;
}

int gcd(int a,int b){
	if(!b) return a;
	return gcd(b,a%b);
}

void Insert(int x,int y){
	int key=(x*10003+y)%MAXN;
	if(key<0) key+=MAXN;
	while(hs[key].cnt!=0){
		long long t1=x,t2=y;
		t1*=hs[key].b;
		t2*=hs[key].a;
		if(t1==t2) break;
		key=(key+1)%MAXN;
	}
	if(hs[key].cnt==0){
		hs[key].a=x;
		hs[key].b=y;
	}
	hs[key].cnt++;
	ans=max(ans,hs[key].cnt);
	return;
}

void Solve(){
	int i,j,k;
	ans=0;
	for(i=0;i<n;i++){
		memset(hs,0,sizeof(hs));
		for(j=0;j<n;j++){
			if(i==j) continue;
			int tx=abs(px[i]-px[j]);
			int ty=abs(py[i]-py[j]);
			int g=gcd(tx,ty);
			if(g!=0){
				tx/=g,ty/=g;
			}
			Insert(tx,ty);
		}
	}
	printf("%d\n",ans+1);
	return;
}

int main()
{
	freopen("in.txt","r",stdin);
	while(Input()){
		Solve();
	}
	return 0;
}