1118.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 1003
typedef struct
{
	long x,y,total;
}data;
data p[NMAX];
int w[NMAX];
int total[NMAX];
int N;

typedef struct
{
	long x,y,ix,iy;
}direct;
direct a[NMAX][NMAX];
/*
void init()
{
	int i;
	for(i=0;i<=w;i++)
		w[i]=i*(i-1);
}*/
void set(int i,int j)
{
	a[i][j].x=p[i].x-p[j].x;
	a[i][j].y=p[i].y-p[j].y;
	a[i][j].ix=i;
	a[i][j].iy=j;
}
int cross(direct t1,direct t2)
{
	return t1.x*t2.y-t1.y*t2.x;
}
int cmp(const void *a,const void *b)
{
	direct *t1=(direct*)a,*t2=(direct*)b;
	if(t1->x==0&&t1->y==0)
		return -1;
	if(t2->x==0&&t2->y==0)
		return 1;
	return cross(*t1,*t2);
}

void solve()
{
	int i,j;
	memset(a,0,sizeof(a));
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			if(i==j)
				continue;
			set(i,j);

		}
	}
	int max=-1;
	int total;
	int same;
	for(i=0;i<N;i++)
	{
		qsort(a[i],N,sizeof(direct),cmp);
		same=-1;
		total=0;
		j=0;
		while(a[i][j].x==0&&a[i][j].y==0)
		{
			j++;
			same++;
		}
		total=1;
		for(++j;j<N;j++)
		{
			
			if(cross(a[i][j],a[i][j-1])==0)
				total++;
			else
			{
				if(max<same+total)
					max=same+total;
				total=1;
			}
		}
		if(max<same+total)
			max=same+total;
	}
	printf("%d\n",max+1);


	
		
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,k,j;
	data tmp;
	while(1)
	{
		scanf("%d",&N);
		if(!N)
			break;
		memset(p,0,sizeof(p));
		if(!N)
			break;
		k=0;
		for(i=0;i<N;i++)
		{
			scanf("%d%d",&tmp.x,&tmp.y);
			p[i]=tmp;
		}

		solve();
	}		
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}