洛谷【P1142】轰炸

我对状态空间的理解：https://www.cnblogs.com/AKMer/p/9622590.html

题目传送门：https://www.luogu.org/problemnew/show/P1142

这题可谓十分暴力了……

直接\(n^2\)枚举两个点确定一条直线，然后再\(O(n)\)去计算在这条直线上的点。

总复杂度\(n^3\)，并且涉及大量\(double\)类型运算，换\(CCF\)老年机绝对\(TLE\)

但是洛谷应该是有矿……为我这种追求暴力之美的人提供了良好的环境。

时间复杂度：\(O(n^3)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

int n,ans;

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct point {

    double x,y;

}p[705];

void calc(int a,int b) {

    int res=0;

    for(int i=1;i<=n;i++)

        if(p[i].y==(p[a].y-p[b].y)/(p[a].x-p[b].x)*p[i].x+p[a].y-(p[a].y-p[b].y)/(p[a].x-p[b].x)*p[a].x)res++;

    //(p[a].y-p[b].y)/(p[a].x-p[b].x)是直线的斜率，p[a].y-(p[a].y-p[b].y)/(p[a].x-p[b].x)*p[a].x是直线的截距。之所以直接写在if语句内是为了保证精度。如果先用两个long double类型的变量存下来都不行，不信你可以试试。

    ans=max(ans,res);

}

int main() {

    n=read();

    for(int i=1;i<=n;i++)

        cin>>p[i].x>>p[i].y;//读入

    for(int i=1;i<n;i++)

        for(int j=i+1;j<=n;j++)//n方枚举直线

            calc(i,j);//计算直线

    printf("%d\n",ans);

    return 0;

}