题目有点长

就不搬过来了

写之前一直觉得很难

写了之后才发现也不是特别难

其实就是状压dp，预处理出取某两个猪可以消除哪些其他的猪，然后对于每个状态，找到第一个没有消除的猪（贪心，因为迟早要杀死它），枚举它和哪个配对，复杂度O(2^n * n*n)。

了解了一波精度问题

不是所有的小数都是能用二进制表示的

所以会产生精度问题

一般取个eps=1e-10

然后注意判a<0时要用a<-eps

刚开始写了a<=eps

很明显是错误的

我竟然没发现

然后注意有一种情况是单独加一个点的

因为可能没有其他的点可以跟它凑一个抛物线

#include
    
     #include
     
      #include
      
       #include
       
        struct node{	double x,y;}e[20];int g[20][20];int f[300000];const double eps=1e-10;int main(){	int t,n,m;	double a,b;	scanf("%d",&t);	while(t--)	{		memset(g,0,sizeof(g));memset(f,127,sizeof(f));		scanf("%d %d",&n,&m);		for(int i=1;i<=n;i++)		scanf("%lf %lf",&e[i].x,&e[i].y);		for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)		if(i!=j)		{			a=(e[i].y*e[j].x-e[j].y*e[i].x)/(e[i].x*e[j].x*(e[i].x-e[j].x));			b=(e[j].x*e[j].x*e[i].y-e[i].x*e[i].x*e[j].y)/(e[i].x*e[j].x*(e[j].x-e[i].x));			if(a<-eps)					{				for(int k=1;k<=n;k++)				if(fabs(a*e[k].x*e[k].x+b*e[k].x-e[k].y)<=eps)	g[i][j]|=1<<(k-1);			}		}		f[0]=0;int top=(1<<(n))-1;		for(int i=0;i<=top;i++)		{				int j=1;			while(i&(1<<(j-1)))	j++;			if(j>n)	continue;			f[i|(1<<(j-1))]=std::min(f[i|(1<<(j-1))],f[i]+1);			for(int k=j+1;k<=n;k++)			f[i|g[j][k]]=std::min(f[i|g[j][k]],f[i]+1);		}		printf("%d\n",f[top]);	}	return 0;}