题目描述
Kiana 最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y=ax2+bx 的曲线，其中 a，b 是 Kiana 指定的参数，且必须满足 a＜0。
当小鸟落回地面（即x轴）时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xixi,yiyi) 。
如果某只小鸟的飞行轨迹经过了(xixi,yiyi)，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；
如果一只小鸟的飞行轨迹没有经过(xixi,yiyi)，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。
例如，若两只小猪分别位于 (1,3) 和 (3,3) ，Kiana 可以选择发射一只飞行轨迹为 y=-x2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
可以爆搜也可以状压dp
先枚举两只猪的情况，看是不是开口向下的抛物线，再枚举第三只猪，利用玄学行列式计算是否在这条抛物线上
其他的就是状压dp的基操了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #define ll long long using namespace std; const int maxn=262150; inline int read(){ int x=0,k=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return k*x; } int t,n,m,f[maxn]; double x[20],y[20]; void pd(int x){ for(int i=0;i<(1<<n);i++) f[i|x]=min(f[i|x],f[i]+1); } bool in(int i,int j,int k){ double s=0; s+=x[i]*x[i]*x[j]*y[k]; s+=x[j]*x[j]*x[k]*y[i]; s+=x[k]*x[k]*x[i]*y[j]; s-=x[i]*x[i]*x[k]*y[j]; s-=x[j]*x[j]*x[i]*y[k]; s-=x[k]*x[k]*x[j]*y[i]; return s==0; } int main(){ // freopen(".in","r",stdin); // freopen(".out","w",stdout); t=read(); while(t--){ memset(f,127,sizeof(f)); f[0]=0; n=read();m=read(); for(int i=0;i<n;i++){ cin>>x[i]>>y[i]; x[i]=(int)(x[i]*100+0.5); y[i]=(int)(y[i]*100+0.5); } for(int i=0;i<n;i++){ pd(1<<i); for(int j=0;j<n;j++){ if(x[j]>x[i]&&y[i]*(x[j]-x[i])>x[i]*(y[j]-y[i])){ int b=(1<<i)|(1<<j); for(int k=0;k<n;k++){ if(in(i,j,k)){ b|=(1<<k); } } pd(b); } } } cout<<f[(1<<n)-1]<<endl; } return 0; }