UVa 270 - Lining Up

 

 Lining Up 

``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

1

 

1 1

2 2

3 3

9 10

10 11

Sample Output

3

 本以为这题用枚举会超时 结果却过了，给了我一个小惊喜。 只是此题要注意的时候 输入的做标可能有负的

[cpp] 

#include <stdio.h>  

#include <string.h>  

#include <math.h>  

#define EQS 1e-7  

struct  

{  

    double x,y;  

}a[10000];  

char s1[10000];  

int main()  

{  

    int i,j,n,m,t,l,tag,max,z,s;  

    double k1,d1,x1,y1,x2,y2,x3,y3;  

    scanf("%d%*c",&t);  

    gets(s1);  

    while(t--)  

    {  

        n=0;  

        while(gets(s1))  

        {  

            l=strlen(s1);  

            if(l==0)  

            {  

                break;  

            }  

            if(s1[0]=='-')  

            {  

                i=1;  

            }else  

            {  

                i=0;  

            }  

            for(s=0;i<=l-1;i++)  

            {  

                if(s1[i]==' ')  

                {  

                    break;  

                }  

                s=s*10+s1[i] - '0';  

            }  

            if(s1[0]=='-')  

            {  

                s=s*-1;  

            }  

            a[n].x= (double)s;  

            if(s1[i+1]=='-')  

            {  

                j=i+2;  

            }else  

            {  

                j=i+1;  

            }  

            for(s=0;j <= l-1; j++)  

            {  

                s=s*10 + s1[j]- '0';  

            }  

            if(s1[i+1]=='-')  

            {  

                s=s*-1;  

            }  

            a[n].y= (double)s;  

            n++;  

        }  

        for(i=0,max=0;i<=n-1; i++)  

        {  

            for(j=i+1; j<=n-1;j++)  

            {  

                x1 = a[i].x; y1= a[i].y;  

                x2 = a[j].x; y2= a[j].y;  

                if(fabs(x2 -x1)<=EQS)  

                {  

                    tag=0;  

                    d1=x1;  

                }else  

                {  

                    tag=1;  

                    k1= (y2 - y1)/(x2 - x1);  

                    d1= y1 - k1 * x1;  

                }  

                for(z= j+1,s=2;z<=n-1; z++)  

                {  

                    if(z==i||z==j)  

                    {  

                        continue;  

                    }  

                    x3= a[z].x; y3= a[z].y;  

                    if(tag==0&&fabs(x3-x1)<=EQS)  

    &n

补充：软件开发 , C++ ,