注：本文中绿鸟==猪！
这道题开始一看数据范围我们就知道是一道状压dp，因为绿鸟仅有18个，但是开始看(m)好像没太懂什么意思。既然确定了是状压，那就来设计状态，一般状压的状态肯定是要有二进制的串的，可能还会有其他，但是这个题好像没有别的参数需要记录，暂且设(0)为绿鸟没有被打，(1)表示绿鸟已经死亡，(f[i])表示状态为(i)时所需要的最少的鸟数来打诶我刚才在说什么绿鸟。
考虑转移，想转移的时候大概有一个模糊的概念：一个状态或（(or)）上另一个状态等于一个状态(+1)。但是又对题目中给出的抛物线产生了疑惑（怎么搞出来的），后来通过捡起放下很久的解析几何芝士想到好像这个抛物线仅有(a,b)两个参数且(a<=0)，这样两点就能确定一条抛物线..之后的思路有点混乱，感觉无法把两者结合在一起，我还是太菜了==。
一种想法是(O(T*2^n*n^2))的算法。我们先预处理出每根抛物线，求出每条抛物线打绿鸟对应的状态。然后转移的时候枚举每根抛物线就好。怎么处理抛物线？先两两枚举点，解出他们的抛物线，然后注意横坐标相同的两点不可解（因为差值为0，之后会整数被0除），最后再记录一下只有一个点在的抛物线。
还有是要注意下精度问题：这是自己绝对想不到的。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 400090
using namespace std;
const double eps=1e-8;
int T,n,m,tot,fake;
int lin[maxn],f[maxn],vis[100];
struct point{
double x,y;
}p[100];
void calc(int i,int j)
{
double a=(p[j].x*p[i].y-p[j].y*p[i].x)/(p[i].x*p[j].x*(p[i].x-p[j].x));
if(a>=0) return ;
double b=p[j].y/p[j].x-a*p[j].x;
tot++;
for(int k=1;k<=n;k++)
{
double qwq=p[k].x*p[k].x*a+b*p[k].x;
if(qwq-p[k].y>=eps||p[k].y-qwq>=eps) continue;
lin[tot]|=(1<<(k-1));vis[k]=1;
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
tot=0;
memset(lin,0,sizeof(lin));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(p[i].x!=p[j].x) calc(i,j);
for(int i=1;i<=n;i++)
if(!vis[i]) lin[++tot]=(1<<(i-1));
memset(f,0x3f,sizeof(f));
f[0]=0;
fake=(1<<n)-1;
for(int i=0;i<=fake;i++)
for(int j=1;j<=tot;j++)
f[i|lin[j]]=min(f[i|lin[j]],f[i]+1);
printf("%d
",f[fake]);
}
return 0;
}