題目?jī)?nèi)容：

Description

“不要問我太陽(yáng)有多高?
我會(huì)告訴你我有多真?
不要問我星星有幾顆?
我會(huì)告訴你很多很多”?

一天Qinz和wudired在天上數(shù)星星，由于星星可以排列成一條直線，他們比賽看誰能找到一條直線使得這條直線上的星星最多。假設(shè)夜空是一個(gè)二維平面坐標(biāo)系，坐標(biāo)軸為x，y。星星的坐標(biāo)(x,y)為整數(shù)，且同一位置至多有一顆星星。他們需要你的幫助，一條直線最多可以穿過多少顆星星（直線不必平行于坐標(biāo)軸）？

Input 多組數(shù)據(jù)，EOF結(jié)束。?
　　第一行N(0<=N<=1000)為天上星星的數(shù)量。?
　　接下來N行每行兩個(gè)數(shù)字 X，Y(0<=X,Y<=10^9)，表示星星的位置。以空格分開。 Output 輸出一行，表示一條直線最多穿過多少顆星星。 Sample Input 3
1 1
2 2
3 3 Sample Output 3 解題思路： 從每個(gè)點(diǎn)當(dāng)作起始點(diǎn)，計(jì)算和其他點(diǎn)之間的斜率，如果一點(diǎn)A，到B和C斜率的絕對(duì)值相同，那么這三個(gè)點(diǎn)在一條線上，以此類推，算出在同一條直線上最多的點(diǎn)數(shù) 代碼如下： 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <math.h> 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/liucheng/p/3683141.html

總結(jié)

以上是生活随笔為你收集整理的题解西电OJ (Problem 1008 - 数星星)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。