题目
题目链接：https://www.luogu.com.cn/problem/P2831
Kiana 最近沉迷于一款神奇的游戏无法自拔。
简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于 \((0,0)\) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 \(y=ax^2+bx\) 的曲线，其中 \(a,b\) 是 Kiana 指定的参数，且必须满足 \(a < 0\)，\(a,b\) 都是实数。
当小鸟落回地面（即 \(x\) 轴）时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有 \(n\) 只绿色的小猪，其中第 \(i\) 只小猪所在的坐标为 \(\left(x_i,y_i \right)\)。
如果某只小鸟的飞行轨迹经过了 \(\left( x_i, y_i \right)\)，那么第 \(i\) 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；
如果一只小鸟的飞行轨迹没有经过 \(\left( x_i, y_i \right)\)，那么这只小鸟飞行的全过程就不会对第 \(i\) 只小猪产生任何影响。
例如，若两只小猪分别位于 \((1,3)\) 和 \((3,3)\)，Kiana 可以选择发射一只飞行轨迹为 \(y=-x^2+4x\) 的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有 \(T\) 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
思路
显然设 \(f[s]\) 表示已经打掉的猪的集合为 \(s\) 所需的步数。
预处理出 \(S[i][j]\) 表示 猪 \(i,j\) 坐标以及 \((0,0)\) 所构成的抛物线能打到的猪的集合。转移时枚举两个猪转移即可。
时间复杂度 \(O(n^22^n)\)。
代码
#include <bits/stdc++.h>
#define reg register
using namespace std;
const int N=20,M=(1<<18)+10;
const double eps=1e-8;
int Q,n,ans,type,S[N][N],f[M],cnt[M];
double X[N],Y[N];
void prework()
{
memset(f,0x3f3f3f3f,sizeof(f));
memset(S,0,sizeof(S));
f[0]=0; ans=114514;
}
int main()
{
cnt[0]=0;
for (reg int i=1;i<M;i++)
cnt[i]=cnt[i-(i&-i)]+1;
scanf("%d",&Q);
while (Q--)
{
prework();
scanf("%d%d",&n,&type);
for (reg int i=1;i<=n;i++)
scanf("%lf%lf",&X[i],&Y[i]);
for (reg int i=1;i<=n;i++)
for (reg int j=1;j<=n;j++)
{
double rate=X[j]/X[i];
double a=(rate*Y[i]-Y[j])/(rate*X[i]*X[i]-X[j]*X[j]);
double b=(Y[i]-a*X[i]*X[i])/X[i];
if (a>=0 || X[i]==X[j]) continue;
for (reg int k=1;k<=n;k++)
if (fabs(Y[k]-a*X[k]*X[k]-b*X[k])<=eps) S[i][j]|=(1<<k-1);
}
int Maxn=(1<<n);
for (reg int s=0;s<Maxn;s++)
for (reg int i=1;i<=n;i++)
for (reg int j=1;j<=n;j++)
if (S[i][j]) f[s|S[i][j]]=min(f[s|S[i][j]],f[s]+1);
for (reg int i=0;i<Maxn;i++)
ans=min(ans,f[i]+n-cnt[i]);
printf("%d\n",ans);
}
return 0;
}