记忆化搜索：

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 18, M = 1 << 18;
const double eps = 1e-6;
typedef pair <double, double> PDD;
int n, m;
PDD q[N];
int path[N][N];
int f[M];

int cmp(double x, double y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

int dfs(int state)
{
    if(state + 1 == 1 << n) return f[state] = 0;

    if(f[state]) return f[state];

    int t;
    for(int i = 0; i < n; i++)
    {
        if(!(state >> i & 1))
        {
            t = i;
            break;
        }
    }

    int res = n * n;
    for(int i = 0; i < n ;i ++)
    {
        if(path[t][i] == 0) continue;
        res = min(res, dfs(state | path[t][i]) + 1);

    }
    return f[state] = res;
}
int main()
{

    int T;
    cin >> T;
    while(T --)
    {
        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(!cmp(x1, x2)) continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 -  a * x1;

                if(cmp(a, 0) >= 0) continue;
                int state = 0;
                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, 0, sizeof f);
        cout << dfs(0) << endl;
    }

    
    return 0;
}

/*
一般抛物线方程： y = ax^2 + bx + c;

1.过原点 c = 0
2.开口向下 a < 0

y = ax^2 + bx
此时需要两点可以确定一条抛物线

一共只有n^2个不同的抛物线。

接下来求出所有不同的抛物线，以及能覆盖的所有点的点集。

此问题就可以转化为了经典重复覆盖问题，即给定01矩阵，要求选择尽量少的行，
将所有列覆盖。 标准算法是Dancing Links

由于n <= 18,我们可以直接使用状态压缩dp求解，代码更简单。

f[i] 表示当前已经覆盖的列是i时的最小行数
f[i | j] = min(f[i | j], f[i] + 1);


*/

状态压缩DP

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 18, M = 1 << 18;
const double eps = 1e-8;
typedef pair <double, double> PDD;
int n, m;
PDD q[N];
int path[N][N];
int f[M];

int cmp(double x, double y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

// int dfs(int state)

int main()
{

    int T;
    cin >> T;
    while(T --)
    {
        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(!cmp(x1, x2)) continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 -  a * x1;

                if(cmp(a, 0) >= 0) continue;

                int state = 0;
                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;

        // cout << dfs(0) << endl;
        // return 0;

        for(int i = 0; i + 1 < 1 << n; i ++)
        {
            int x = 0;
            for(int j = 0; j < n; j++)
                if(!(i >> j & 1))
                    {
                        x = j;
                        break;
                    }
            
            for(int j = 0; j < n; j++)
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

        // for(int i = 0; i + 1 < 1 << n; i++)
        //     cout << f[i] << " ";
        cout << f[(1 << n) - 1] << endl;
    }

    
    return 0;
}

/*
一般抛物线方程： y = ax^2 + bx + c;

1.过原点 c = 0
2.开口向下 a < 0

y = ax^2 + bx
此时需要两点可以确定一条抛物线

一共只有n^2个不同的抛物线。

接下来求出所有不同的抛物线，以及能覆盖的所有点的点集。

此问题就可以转化为了经典重复覆盖问题，即给定01矩阵，要求选择尽量少的行，
将所有列覆盖。 标准算法是Dancing Links

由于n <= 18,我们可以直接使用状态压缩dp求解，代码更简单。

f[i] 表示当前已经覆盖的列是i时的最小行数
f[i | j] = min(f[i | j], f[i] + 1);


*/