1196: 數星星（二）（結構體專題）

題目描述

一天，小明坐在院子裡數星星，Gardon就出了個難題給他，讓他數數天上的星星最多有多少個是在同一條直線上的。天上的星星太多了，小明馬上就看花了眼，你能寫個程式來幫他計算麼？

輸入

首先輸入一個整數N(N<=300)，接下來的N對數每對表示一個星星的位置（星星的坐标在-10000到10000之間，精确到小數點後1位）。沒有兩個星星會在同一個位置。

輸出

一個整數，表示一條直線上最多星星的數目。

樣例輸入 Copy

5

0 0

1 0

1 1

0 1

0.5 0.5

樣例輸出 Copy

3

來源/分類

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 301
/*
1.兩點确定一條直線
2.n>3時，先找出兩個點确定一條直線，在剩餘的n-2個點中找出在該直線上點的個數
    存放在數組中，數組大小(n-2)*(n-1)/2
3.判斷第三個點是否與前兩個點在同一條直線上
    (y3-y1)/(x3-x1)=(y3-y2)/(x3-x2)  沒有将斜率不存在包含進去
    (y3-y1)*(x3-x2)==(y3-y2)*(x3-x1) 
*/

typedef struct point{
    double x;
    double y;
}point;



int main(){
    int n,h=0,a[45000]={0},max=0;
    point p[N];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf %lf",&p[i].x,&p[i].y);
    }

    if(n==1) {
        printf("1\n");
        return 0;
    }
    if(n==2) {
        printf("2\n");
        return 0;
    }
    
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                if((p[k].y-p[i].y)*(p[k].x-p[j].x)-(p[k].x-p[i].x)*(p[k].y-p[j].y)==0)
                    a[h]++;
            }
            h++;
        }
    }

    for(int i=0;i<h;i++){
        if(a[i]>max) max=a[i];
    }
    printf("%d\n",max+2);
    return 0;
}