UVa 270 - Lining Up

链接：

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

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)