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;
}