poj1118(Lining Up)

 題目大意是這樣:給出n個點的坐标，判斷在這些點中最多有多少個點共線。。。

我開始的思路是用暴力，找出前兩個點的連線然後再從生下的點中找出斜率相同的點記錄并且統計個數，最後找出統計的個數中最大的，時間複雜度是O(n^3)資料最大是700，是以我開始希望可以險過，可是結果沒過，是以我就又換了一種思路重新思考，對于從每個起點開始，記錄每種斜率的個數，最後傳回最大值，這種算法隻用了O(n^2)

Lining Up

Time Limit: 2000MS	Memory Limit: 32768K
Total Submissions: 15964	Accepted: 5003

Description

"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

Input consist several case,First line of the each case is an integer N ( 1 < N < 700 ),then follow N pairs of integers. Each pair of integers is separated by one blank and ended by a new-line character. The input ended by N=0.

Output

output one integer for each input case ,representing the largest number of points that all lie on one line.

Sample Input

5
1 1
2 2
3 3
9 10
10 11
0      

Sample Output

3      

***********************、、、、、、逾時代碼、、、、、、、、、、、、、***********

#include<cstdio>
#include<iostream>

using namespace std;

struct point{
    int x,y;
}dian[750];
int n;

double xielv(point p1, point p2){
    return (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
}
int cal_xielv(){
    int max = 0;
    int geshu;
    for(int i = 0; i < n - 1;i++){
        if(n - i < max){break;}
        for(int j =  i + 1; j < n; j++){
            geshu = 2;
            if(n - j < max){break;}
            for(int k = j + 1; k < n; k++){
                if(dian[i].x == dian[j].x){
                    if(dian[j].x == dian[k].x){
                        geshu++;
                    }
                }
                else if(xielv(dian[i],dian[j]) == xielv(dian[j], dian[k])){
                    geshu++;
                }
            }
            if(geshu > max)  max = geshu;
        }
    }
    return max;
}
int main(){
    while(scanf("%d", &n)&&n!=0){
        for(int i = 0; i < n; i++){
            scanf("%d%d", &dian[i].x, &dian[i].y);
        }
        printf("%d\n", cal_xielv());
    }
    return 0;
}
           

以下為AC代碼：

708K

313MS

開始的時候我把max初始化為0，造成了一個很難查找的錯誤，是以接着就很長一串wa，真是悲劇啊，下次注意了、、、、、、、

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct point{
    int x,y;
}dian[750];
int n;
const int INF = 0x7fffffff;
double lie_xie[750];
double xielv(point p1, point p2){
    return (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
}

int cmp(const void *a,const void *b){
    return *(double *)a > *(double *)b ? 1 : -1;
}
int cal_xielv(){
    int max = 2;
    int geshu;
    for(int i = 0; i < n;i++){
        geshu = 2;
        int xienum = 0;//斜率個數
        for(int j = i + 1; j < n; j++){
            if(dian[i].x == dian[j].x){
                lie_xie[xienum++] = INF;
            }
            else {
                lie_xie[xienum++] = xielv(dian[i], dian[j]);
            }
        }
        qsort(lie_xie,xienum,sizeof(lie_xie[0]),cmp);
        for(int k = 0; k < xienum - 1;k++){
            if(lie_xie[k] == lie_xie[k + 1]){
                ++geshu;
                if(geshu > max)  max  = geshu;
            }
            else geshu = 2;
        }
    }
    return max;
}
int main(){
    while(scanf("%d", &n)&&n!=0){
        for(int i = 0; i < n; i++){
            scanf("%d%d", &dian[i].x, &dian[i].y);
        }
        printf("%d\n", cal_xielv());
    }
    return 0;
}