Luogu P2831

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 20
using namespace std;

const double eps=1e-8;
int T,m,n;
double x[M],y[M];
int dp[1<<20];
int L[M][M];

bool Equ(double x,double y){
	double tmp=fabs(x-y);
	if(tmp<=eps)
		return true;
	else return false;
}

void Getline(double &rx,double &ry,int i,int j){
	double a1=x[i]*x[i],b1=x[i],c1=y[i];
	double a2=x[j]*x[j],b2=x[j],c2=y[j];
	ry=(c1*a2-c2*a1)/(b1*a2-b2*a1);
	rx=(c1-b1*ry)/a1;
}

bool Online(int yyc,double a,double b){
	double xi=x[yyc],yi=y[yyc];
	if(Equ(yi,a*xi*xi+b*xi))
		return true;
	return false;
}

int main(){
	scanf("%d",&T);
	while(T--){
		memset(L,0,sizeof(L));
		memset(dp,0x3f3f3f3f,sizeof(dp));
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&x[i],&y[i]);
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++){
				if(Equ(x[i],x[j])) continue;
				double a,b;
				Getline(a,b,i,j);
				if(a>-eps) continue;
				for(int k=0;k<n;k++)
					if(Online(k,a,b)) L[i][j]|=(1<<k);
			}
		dp[0]=0;
		for(int i=0;i<(1<<n);i++)
			for(int j=0;j<n;j++){
				dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+1);
				for(int k=0;k<n;k++) dp[i|L[j][k]]=min(dp[i|L[j][k]],dp[i]+1);
			}
		printf("%d\n",dp[(1<<n)-1]);
	}
	return 0;
}