poj2780解题报告

Linearity

Time Limit: 3000MS	Memory Limit: 65536K
Total Submissions: 5999	Accepted: 1287

Description

Alice often examines star maps where stars are represented by points in a plane and there is a Cartesian coordinate for each star. Let the Linearity of a star map be the maximum number of stars in a straight line.

For example, look at the star map shown on the figure above, the Linearity of this map is 3, because the star 1, star 2, and star 5 are within the same straight line, and there is no straight line that passes 4 stars.

You are to write a program to find the Linearity of a star map.

Input

Input will contain multiple test cases. Each describes a star map.

For each test case, the first line of the input contains the number of stars N (2 <= N <= 1000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0 <= X, Y <= 1000). There can be only one star at one point of the plane.

Output

Output the Linearity of the map in a single line.

Sample Input

5
0 0
2 0
0 2
1 1
2 2
      

Sample Output

3      

题意：给定n个点，判断最多有多少个点共线      

思路：把以前写的1118拿出来改了下数组大小交上去了，1100多MS，思路是将每个点分别作为基点，将其余点的      

坐标变换到以这个点为原点的坐标系上，求出每个点在这个坐标系上的斜率然后排序(分母为0的拿出来单独处理)，      

然后一次循环就能判断出多少个点的斜率一样然后再求出最多共线的点。。。      

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
	int n;
	while(cin>>n && n)
	{
		int x[1010],y[1010];     int i,j,k,max=2;
		for(i=1;i<=n;i++)
			scanf("%d%d",&x[i],&y[i]);
		for(k=1;k<=n;k++)
		{
			int ns=1;
			double xy[1010];	int ed=0;
			for(i=1;i<=n;i++)
				if(x[i]-x[k]==0)	ed++;
				else
					xy[ns++]=(double)(y[i]-y[k])/(double)(x[i]-x[k]);
			sort(&xy[1],&xy[ns]);
					
			int zhongjie=2;
			int sum=2;
			double comp=xy[1];
			for(i=2;i<ns;i++)
				if(comp==xy[i])
					sum++;
				else
				{
					comp=xy[i];
					if(sum>zhongjie)	zhongjie=sum;	sum=2;
				}
			if(sum>zhongjie)	zhongjie=sum;

			if(zhongjie>max)   max=zhongjie;	
			if(ed>max)	max=ed;
		}
		cout<<max<<endl;
	}
	return 0;
}