题意分析
注意到 $n\leq18$，因此可以考虑状压 DP。
设 $\textit{dp}_s$ 表示射死的猪的集合为 $s$ 时的方案数。（$s$ 放到状压的代码里面就是一个整数，二进制的第 $i$ 位表示猪 $i$ 是否被射死。）
那么考虑抛物线如何射死猪。
对于一条抛物线，如果射死一只猪，则有无穷多条；如果射死两只猪，则可以确定（因为抛物线形如 $y=ax^2+bx$，必须过点 $(0,0)$）。
那么记 $\textit{line}_{i,j}$ 表示射死第 $i,j$ 只猪的合法的抛物线射死的猪的状态（猪从 $0$ 至 $n-1$ 编号）。
记 $(x_i,y_i),(x_j,y_j)$ 分别为猪 $i,j$ 的坐标。
设 $\textit{line}_{i,j}$ 对应抛物线为 $y=ax^2+bx$，则待定系数法解方程可以确定：
\[\begin{cases} a=\dfrac{x_j\cdot y_i-x_i\cdot y_j}{x_i\cdot x_j(x_i-x_j)}\\ b=\dfrac{y_i}{x_i}-a\cdot x_i \end{cases}\]那么就可以确定哪些猪会被 $\textit{line}_{i,j}$ 对应抛物线射死。
需要注意的是：
- 计算 $\textit{line}_{i,j}$ 时需要特判 $i=j$ 时：此时其状态 $s$ 只包含 $i$，即只射死猪 $i$。
- 算出来的二次函数 $y=ax^2+bx$ 需要满足 $a<0$，否则不是合法抛物线。
还需要注意的是，double 具有误差，因此当两个 double 只差的绝对值小于一定常数的时候，就应当判断其相等；这个常数一般称作 eps，此处取 $10^{-6}$。
对于 DP 的转移，由 $s$ 找到哪些抛物线是新增的显然不太好找，因此可以从已知状态 $s$ 开始向其他状态递推。
即：
\[\textit{dp}_{s\cup\textit{line}_{i,j}}\leftarrow\min(\textit{dp}_{s\cup\textit{line}_{i,j}},\textit{dp}_s+1)\]其中，$\leftarrow$ 表示赋值。当然也有代码版的递推方程：
1
dp[s|line[i][j]]=min(dp[s|line[i][j]],dp[s]+1);
AC 代码
时间复杂度：$\mathcal O\left(Tn^2\log n\right)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=18;
constexpr const double eps=1e-6;
int n,dp[1<<N|1],line[N+1][N+1];
struct node{
double x,y;
}a[N+1];
struct func{
double a,b;
};
func calc(node a,node b){
double& x1=a.x,x2=b.x,y1=a.y,y2=b.y;
func ans;
ans.a=(x2*y1-x1*y2)/(x1*x2*(x1-x2));
ans.b=y1/x1-ans.a*x1;
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
int m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
}
memset(line,0,sizeof(line));
for(int i=0;i<n;i++){
line[i][i]|=(1<<i);
for(int j=0;j<n;j++){
if(i==j){
continue;
}
auto pl=calc(a[i],a[j]);
if(pl.a>=0){
continue;
}
for(int k=0;k<n;k++){
if(abs(a[k].y-(pl.a*a[k].x*a[k].x+pl.b*a[k].x))<=eps){
line[i][j]|=(1<<k);
}
}
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
dp[i|line[j][k]]=min(dp[i|line[j][k]],dp[i]+1);
}
}
}
cout<<dp[(1<<n)-1]<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
