原题链接：https://www.luogu.com.cn/problem/P2831
题意解读：求覆盖平面上所有点的最少的曲线数，曲线形如y=ax2+bx
解题思路：
1、两点确定一条曲线
由于曲线方程为：y=ax2+bx，可以判断两点确定一条曲线
设两点为(x1,y1)，(x2,y2)，则有
y1 = ax12 + bx1，y2 = ax22 + bx2
解方程得到：a = (y1/x1-y2/x2)/(x1-x2)，b = y1/x1 - ax1
可以枚举所有两个点构成的曲线，再将所有点代入方程即可确定每条曲线经过了哪些点，每条曲线经过的点可以用状态压缩存入一个整数
设path[i][j]表示第i、j个点构成的曲线经过的所有点的状态
这里有一个特殊情况，如果两个不同的点构成的曲线a不小于0则不合法，如果所有两点构成的曲线都不合法，经过每一个点至少有一个合法的曲线，也
就是path[i][i] = 1 << i，第i个点必有曲线经过i。
2、搜索
dfs(当前已覆盖的点：stat，用了几条曲线：cnt)
{
if stat表示所有点已覆盖
ans = min(ans, cnt)
return
for 所有当前没有覆盖的点
对于任意一个没有覆盖的点，找到所有经过它的曲线
用曲线经过的点的状态 | stat，得到newstat
继续dfs(newstat, cnt + 1)
break，每次只找一个没有覆盖的点，用所有经过它的曲线去更新状态
}
调用：dfs(0, 0)
3、考虑到性能，可以定义f[i]记录已覆盖点状态为i时经过的最少曲线数，使用记忆化搜索
dfs(当前已覆盖的点：stat，用了几条曲线：cnt)
{
if(f[i] != INF && f[i] <= cnt) return;
f[i] = min(f[i], cnt)
if stat表示所有点已覆盖
ans = min(ans, cnt)
return
for 所有当前没有覆盖的点
对于任意一个没有覆盖的点，找到所有经过它的曲线
用曲线经过的点的状态 | stat，得到newstat
继续dfs(newstat, cnt + 1)
break，每次只找一个没有覆盖的点，用所有经过它的曲线去更新状态
}
4、注意浮点数的比较不能直接用==，应该相减看是否小于一个更小的值
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 18, INF = 0x3f3f3f3f;
const double EPS = 1e-6;
struct Point
{ double x, y;
} points[N];
int path[N][N]; //path[i][j]表示i，j两个点构成的曲线经过的所有点的状态
int f[1 << N]; //f[i]表示经过的所有点的状态为i时所需的最少曲线数
int t, n, m, ans;int cmp(double x, double y)
{if(fabs(x - y) < EPS) return 0;if(x > y) return 1;else if(x < y) return -1;
}void dfs(int stat, int cnt)
{if(f[stat] <= cnt) return; //记忆化+最优性剪枝f[stat] = min(f[stat], cnt);if(stat == (1 << n) - 1) //所有点都已覆盖{ans = min(ans, cnt);return;}for(int i = 0; i < n; i++){if(!(stat >> i & 1)){for(int j = 0; j < n; j++){if(path[i][j]){int newstat = stat | path[i][j];dfs(newstat, cnt + 1);}}break; //每次取一个未被覆盖的点，用经过该点的不同曲线去更新覆盖状态}}
}int main()
{cin >> t;while(t--){memset(path, 0, sizeof(path));cin >> n >> m;for(int i = 0; i < n; i++){cin >> points[i].x >> points[i].y;}for(int i = 0; i < n; i++){path[i][i] = 1 << i; //每个点一定有一条经过它的曲线for(int j = 0; j < n; j++){double x1 = points[i].x, y1 = points[i].y;double x2 = points[j].x, y2 = points[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) != -1) continue; //a必须小于0//找到曲线y=ax^2+bx经过的所有点for(int k = 0; k < n; k++){double x = points[k].x, y = points[k].y;if(!cmp(y, a * x * x + b * x)){path[i][j] |= (1 << k);}}}}ans = INF;memset(f, 0x3f, sizeof(f));dfs(0, 0);cout << ans << endl;}return 0;
}