题目描述

给你n个点，求最多有多少点共线

思路

暴力O(n^3)枚举每个点，然后看是否在同一直线上

#include <stdio.h>
using namespace std;
inline int read(){
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
struct arr
{
    double x,y;
    void intput(){x=read();y=read();}
}edge[400];
arr r;
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        edge[i].intput();   
    int ans=0;
    for (int i=1;i<=n;i++)
    {

        for (int j=i+1;j<=n;j++)
        {
            int t=0;
            for (int k=j+1;k<=n;k++)
                if ((edge[j].x-edge[i].x)*(edge[k].y-edge[j].y)==(edge[j].y-edge[i].y)*(edge[k].x-edge[j].x))
                    t++;
            if (ans<t) ans=t;
        }
    }
    printf("%d\n",ans+2);
}