题目内容：

Description

“不要问我太阳有多高 

我会告诉你我有多真 

不要问我星星有几颗 

我会告诉你很多很多” 

一天Qinz和wudired在天上数星星，由于星星可以排列成一条直线，他们比赛看谁能找到一条直线使得这条直线上的星星最多。假设夜空是一个二维平面坐标系，坐标轴为x，y。星星的坐标(x,y)为整数，且同一位置至多有一颗星星。他们需要你的帮助，一条直线最多可以穿过多少颗星星（直线不必平行于坐标轴）？

Input

　　多组数据，EOF结束。 

　　第一行N(0<=N<=1000)为天上星星的数量。 

　　接下来N行每行两个数字 X，Y(0<=X,Y<=10^9)，表示星星的位置。以空格分开。

Output

　　输出一行，表示一条直线最多穿过多少颗星星。

Sample Input

3

1 1

2 2

3 3

Sample Output

3

 

解题思路：

从每个点当作起始点，计算和其他点之间的斜率，如果一点A，到B和C斜率的绝对值相同，那么这三个点在一条线上，以此类推，算出在同一条直线上最多的点数

 

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 #define MAX_NUM 1000 6  7 int cmp(const void * a , const void * b) 8 { 9     if(*(double *)a > *(double *)b){10         return 1 ;11     }12     return -1 ;13 }14 15 double k(int x , int y , int x1 , int y1)16 {17     if(x == x1){18         return 1E10 ;19     }20     return (double)(y1 - y) / (x1 - x) ;21 }22 23 int cal(int p[][2] , int num)24 {25     if(num < 3 ){26         return num ;27     }28     double line[MAX_NUM] ;29     int res = 0, i , x , y  , j;30     for(i = 0 ; i < num ; i++){31         x = p[i][0] ;32         y = p[i][1] ;33         for(j = i+1 ; j < num ; j++){34             line[j] = k(x,y,p[j][0],p[j][1]) ;35         }36         qsort(line+i+1,num-i-1,sizeof(double),cmp);37         int k = 2 ;38         for(j = i+2 ; j < num ; j++){39             if(fabs(line[j]-line[j-1]) < 1E-10){40                 k++ ;41             }else{42                 if(k+1>res){43                     res = k ;44                 }45                 k = 2 ;    46             }47         }48         if(k>res){49             res = k ;50         }51     }52     return res ;53 }54 55 56 int main()57 {58     int point[MAX_NUM][2] ;59     int i , num;60     while(scanf("%d",&num)!=EOF){61         for(i = 0 ; i < num ; i++){62             scanf("%d%d",&point[i][0],&point[i][1]);63         }64         printf("%d\n",cal(point,num));65     }66 }