链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=206
原题：
``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
更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output consists of one integer representing the largest number of points that all lie on one line.
Sample Input
1 1 1 2 2 3 3 9 10 10 11
Sample Output
3
题目大意：
给出一系列的点， 求最多有多少个点能连成一条线。
分析与总结：
两点确定一条直线， 那么就可以枚举所有的两点情况，然后在根据这两个点确定的一条直线，再遍历其它点，判断有几个点是在这条直线上的。
判断三个点p1(x1,y1),p2(x2,y2),p3(x3,y3)是否是一条直线的方法是，看p1,p2的斜率是否与p2,p3的斜率相等， 数学公式是(x1-x2)/(y1-y2)=(x2-x3)/(y2-y3),但是直接相除比较斜率的话精度会有损失，所以利用对角线想乘法则，可以把这个式子转化成(x1-x2)*(y2-y3)=(y1-y2)*(x2-x3).
接着就是暴力枚举了。
代码：
/*
* UVa: 270 - Lining Up
* Time: 0.888s
* Author: D_Double
*
*/
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 705
using namespace std;
struct Node{
int x,y;
}arr[MAXN];
int nIndex;
char str[1000];
inline void input(){
nIndex=0;
while(gets(str)){
if(!str[0])break;
sscanf(str,"%d%d",&arr[nIndex].x,&arr[nIndex].y);
++nIndex;
}
}
inline bool is_in_line(int X1,int Y1,int X2,int Y2,int X3,int Y3){
return (X1-X2)*(Y3-Y2)-(X3-X2)*(Y1-Y2)==0;
}
void solve(){
int maxNum=2;
for(int i=0; i<nIndex; ++i){
for(int j=i+1; j<nIndex; ++j){
int cnt=2;
for(int k=j+1; k<nIndex; ++k){
if(is_in_line(arr[i].x,arr[i].y,arr[j].x,arr[j].y,arr[k].x,arr[k].y))
++cnt;
}
if(cnt>maxNum) maxNum=cnt;
}
}
printf("%d\n", maxNum);
}
int main(){
int T;
scanf("%d%*c",&T);
gets(str);
while(T--){
input();
if(nIndex==1)printf("1\n");
else if(nIndex==2)printf("2\n");
else solve();
if(T) printf("\n");
}
return 0;
}
作者：csdn博客 shuangde800
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， number
， 直线
， line
， of
The
，以便于您获取更多的相关知识。