UVa 270：Lining Up

UVa 270：Lining Up2014-12-02链接：

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

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

11 12 23 39 1010 11

Sample Output

题目大意：

给出一系列的点，求最多有多少个点能连成一条线。

分析与总结：

两点确定一条直线，那么就可以枚举所有的两点情况，然后在根据这两个点确定的一条直线，再遍历其它点，判断有几个点是在这条直线上的。

判断三个点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 705using 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
", maxNum）;}int main（）{int T;scanf（"%d%*c",&T）;gets（str）;while（T--）{input（）;if（nIndex==1）printf（"1
"）;else if（nIndex==2）printf（"2
"）;elsesolve（）;if（T） printf（"
"）;}return 0;}

作者：csdn博客 shuangde800