首页 > 代码库 > POJ 1118 最多共线点

POJ 1118 最多共线点

2024-07-18 06:24:46   218人阅读

Lining Up
Time Limit: 2000MS Memory Limit: 32768K
Total Submissions: 22516 Accepted: 7091

Description

"How am I ever going to solve this problem?" said the pilot. 

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number? 


Your program has to be efficient! 

Input

Input consist several case,First line of the each case is an integer N ( 1 < N < 700 ),then follow N pairs of integers. Each pair of integers is separated by one blank and ended by a new-line character. The input ended by N=0.

Output

output one integer for each input case ,representing the largest number of points that all lie on one line.

Sample Input

51 12 23 39 1010 110

Sample Output

3




题意：
给n个点坐标，在一条直线上最多点的数目。

思路：
每个点都是要么在答案里，要么不在答案里，先把点按x从小到大排序，然后从最左边开始枚举，求出该点右边或者和该点x相等的点与该点的斜率（该点左边的点就不考虑了，因为之前已经算过了），然后求出斜率相等最多的数目即可。时间差不多就是n*(n-1)/2，交上后94MS，还算可以吧。

代码：
 1 #include <iostream> 2 #include <string> 3 #include <map> 4 #include <stdio.h> 5 #include <math.h> 6 #include <algorithm> 7 using namespace std; 8 #define pi acos(-1) 9 10 struct node{11     double x, y;12 }a[1000];13 14 double k[1000];15 int tot;16 17 bool cmp(node a,node b){18     return a.x<b.x;19 }20 21 main()22 {23      int n, i, j;24      while(scanf("%d",&n)==1&&n){25          26          for(i=0;i<n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);27          sort(a,a+n,cmp);28          int maxh=0, tot;29          for(i=0;i<n;i++){  30              tot=0;31              int mm=0;32              for(j=i+1;j<n;j++){33                  if(a[i].x==a[j].x) mm++;34                  else {35                      k[tot++]=(a[j].y-a[i].y)/(a[j].x-a[i].x);36                  }37              }38              maxh=max(maxh,mm);39              sort(k,k+tot);40              int num=1;41              for(j=1;j<tot;j++){42                  if(k[j]==k[j-1]) num++;43                  else if(k[j]!=k[j-1]){44                      maxh=max(maxh,num);45                      num=1;46                  }47              }48              maxh=max(maxh,num);49              if(n-i-1<=maxh) break;         //若剩余的点数目小于等于maxh，那么就跳出，因为最大也不超过maxh 50          }51          printf("%d\n",maxh+1);52      }53 }

 


联系
我们