算法思路

抛物线方程的特性

• 一般抛物线方程： ( $y = ax^2 + bx + c$ )
• 题目中的抛物线特点：
  1. 过原点，即 ( $c = 0$ )
  2. 开口向下，即 ( $a < 0$ )
• 简化后的抛物线方程： ( $y = ax^2 + bx$ )，有两个未知数，因此两点即可确定一条抛物线。

预处理

• 最多有 ( $n^2$ ) 个不同的抛物线。
• 遍历所有点对，计算每条抛物线的参数 ( $a$ ) 和 ( $b$ )。
• 对于每条抛物线，检查其他点是否在这条抛物线上，从而确定每条抛物线能覆盖的点集。

状态压缩动态规划（DP）

• 状态定义：f[i] 表示当前已经覆盖的点集为 i 时的最小抛物线数量。
• 状态转移：
  • 找到当前未被覆盖的某一列 ( x )，然后枚举所有包含 ( x ) 的抛物线 ( j )。
  • 更新状态：f[i | j] = min(f[i | j], f[i] + 1)。

时间复杂度

• 预处理：需要枚举所有点对来确定抛物线，然后枚举其余点是否在抛物线上，计算量是 ( $O(n^3)$ )。
• 状态压缩DP：一共有 ( $2^n$ ) 个状态，每个状态需要 ( $O(n)$ ) 的计算量，因此每个Case的时间复杂度是 ( $O(n^3 + n^2 cdot 2^n)$ )。
• 总时间复杂度： ( $O(T(n^3 + n^2 cdot 2^n))$ )。

#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> PDD;
#define x first
#define y second

const int N=18,M=1<<18;
const double eps=1e-8;
int n,m;
PDD q[N];
int path[N][N];//表示i和j可以确定的抛物线可以通过的点
int f[M]; //f[state] 穿过state这些点需要几条抛物线
int cmp(double x,double y)
{
    if(abs(x-y)<eps) return 0;
    if(x<y) return -1;
    return 1;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>q[i].x>>q[i].y;
        }
        memset(path,0,sizeof path);
        for(int i=0;i<n;i++)
        {
            path[i][i]=1<<i;
            for(int j=0;j<n;j++)
            {
                double x1=q[i].x,y1=q[i].y;
                double x2=q[j].x,y2=q[j].y;
                if(x1==x2) continue;//x1==x2则一定不可能
                double a=(y1/x1-y2/x2)/(x1-x2);
                double b=y1/x1-a*x1;
                if(a>=0) continue;//需要a<0
                int state=0; //(i,j)缺点的抛物线可以走到的点
                for(int k=0;k<n;k++)
                {
                    double x=q[k].x,y=q[k].y;
                    if(!cmp(a*x*x+b*x,y))  //浮点数比较的时候有误差
                    {
                        state+=1<<k;
                    }
                }
                path[i][j]=state;
            }
        }
        memset(f,0x3f,sizeof f);
        f[0]=0;//还没有穿过
        for(int i=0;i<1<<n;i++)
        {
            int x=0;
            for(int j=0;j<n;j++)
            {
                if(!(i>>j&1)) //当前i没有包含j
                {
                    x=j;
                    break;
                }
            }
            for(int j=0;j<n;j++)
            {
                f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1);//在i的基础上加一条抛物线
            }
        }
        cout<<f[(1<<n)-1]<<endl;
    }
    return 0;
}