题面

这种数据范围不是乱搞dfs就是乱搞状压DP

首先应该通过任一方式求出a和b的值；

任意一条抛物线只用两头猪就可以确定，所以我们N^2枚举，并把在这两头猪的抛物线上的猪都存进状态state[i][j];

然后枚举任意两个还没消灭的小猪i，j；f[i|state[j][k]]=min(f[i|state[j][k]],f[i]+1);

因为有些小猪只能单独被消灭，所以：f[i|(1<<j-1)]=min(f[i|(1<<j-1)],f[i]+1);

然后就好了：

#include
#define eps 1e-7
#define inc(i,a,b) for(register int i=a;i<=b;i++) using namespace std; struct node{ double x; double y; }pig[20]; int f[1000010]; int bo[21]; int n,m; int work(int pig1,int pig2) { if(pig[pig1].x==pig[pig2].x) return 0; double x1=pig[pig1].x,x2=pig[pig2].x,y1=pig[pig1].y,y2=pig[pig2].y; double tmpx=x1*x1*x2-x2*x2*x1,tmpy=y1*x2-y2*x1; double a=tmpy/tmpx,b=(y1-a*x1*x1)/x1; if(a>=0) return 0;
int res=0; bo[pig1]=bo[pig2]=1;
inc(i,1,n){
double x=pig[i].x,y=pig[i].y;
if(fabs(a*x*x+b*x-y)>t;
while(t--){
memset(f,0x3f,sizeof(f));
memset(state,0,sizeof(state));
memset(bo,0,sizeof(bo));
scanf("%d%d",&n,&m);
inc(i,1,n) scanf("%lf%lf",&pig[i].x,&pig[i].y),f[1<>j-1)&1==1)continue;
inc(k,1,j-1){
if(i&(1<<k-1)==1) continue;
f[i|state[j][k]]=min(f[i|state[j][k]],f[i]+1);
}
f[i|(1<<j-1)]=min(f[i|(1<<j-1)],f[i]+1);
}
cout<<f[(1<<n)-1]<<endl;
}
}