题目突破要点：
1.发现最多有18头猪，(*￣(oo)￣)，这么小的数据范围提示我们，这个题要么用搜索要么用状压；
2.如果搜索，那么每次枚举任意两头猪，找到一条抛物线，然后判断抛物线总共经过几头猪，找到最优抛物线，即最优方案
3.但是我们发现这样的做法明显时间复杂度超了，所以对于正解，我们考虑状压
正解：
我们用二进制表示当前位置上的猪是否被打掉，那么由于我们最后的dp转移与小猪的位置有关，所以我们预处理出每一种方案的第一个0的位置（也就是找到第一个打下的小猪是第几个），这样的方法可以降低我们的时间复杂度（看到后面就理解了）
之后我们枚举每一头猪，循环枚举它和剩下的猪构成的抛物线，如果a>0，那么一定没有解（物理规律）。之后再次枚举小猪，判断这个小猪是不是在当前抛物线上，如果是，那么我们设置这个小猪可以被打掉
for(int k=1; k<=n; k++){
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<e) lin[i][j]|=(1<<(k-1));//这一个小猪可以打掉
//lin[i][j]表示第ij个小猪决定的曲线打下猪的状态}
到这，我们的****预处理部分算是真正做好了，接下来就是dp了。总共有1<<n 种方案，我们判断分别每一种方案。先找到每种方案打下来的第1头小猪的编号，那么这头猪后面的猪要么是选择和这头猪在一条抛物线上，要么是新开一条抛物线打猪
之后我们处理每一只猪，对于第i种方案，表示我们已经有了这种方案，如果我们要打另一只小猪，那么我们的状态应该跟着转移，判断到底是用这条抛物线打猪好还是从i的状态上再打一头猪好。
全部转移完成后，输出 cout<<dp[(1<<n)-1]<<'
';
#include<bits/stdc++.h>
#define maxn 1<<19
using namespace std;
const double e=1e-8;
int t,n,m,dp[maxn],lin[19][19],start[maxn];
double x[maxn],y[maxn];
void find(double &a,double &b,int i,int j) {
a=-(y[i]*x[j]-y[j]*x[i])/(x[j]*x[j]*x[i]-x[i]*x[i]*x[j]);
b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[i]*x[i]*x[j]);
}
int main() {
for(int i=0; i<(1<<18); i++) {
int j=1;
for(; j<=18 && i&(1<<(j-1)); j++);
start[i]=j;
}
/*对于每一个状态，我们从他的第一位开始穷举，
i&(1<<(j-1))意思就是i这个状态的第j头pig是否被打掉。
于是start[i]的意思就是i这个状态内第一个0的位置，也就是我们做dp的起始位置。
*//*for(int i=0;i<(1<<18);i++)
{
int j=1;
for(;j<=18 && i&(1<<(j-1));j++)
{
start[i]=j;
}//找到第i个状态的第一只打掉的小猪在哪里
}*/
cin>>t;
while(t--) {
memset(lin,0,sizeof(lin));
memset(dp,1,sizeof(dp));
dp[0]=0;
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
/* for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(fabs(x[i]-x[j])<e) continue;
double a,b;
find(a,b,i,j);
if(a>-e) continue;
for(int k=1;k<=n;k++)
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<e)
lin[i][j]|=(1<<(k-1));
}*/
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(fabs(x[i]-x[j])<e) continue;
double a,b;
find(a,b,i,j);
if(a>-e) continue;//a>0
for(int k=1; k<=n; k++) {
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<e) lin[i][j]|=(1<<(k-1));//这一个小猪可以打掉
}
}
for(int i=0; i<(1<<n); i++) {
int j=start[i];
dp[i|1<<(j-1)]=min(dp[i|1<<(j-1)],dp[i]+1); //先预处理一下j
//找到这个抛物线第一个打下来的猪的位置，打下这些猪的最小
//花费就是打下这头猪时候的花费或者是先打下第i头猪再打第一头猪的花费+1
for(int k=1; k<=n; k++) {
dp[i|lin[j][k]]=min(dp[i|lin[j][k]],dp[i]+1);
}
}
cout<<dp[(1<<n)-1]<<'
';
}
return 0;
}