记录编号	608846	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	6.310 s
提交时间	2025-10-29 21:08:16	内存使用	4.87 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const double eps=1e-8;
const int N=(1<<18);
int T,n,o,dp[N];
double x[20],y[20];
int line[20][20];
double fabs(double v){
	return v<0?-v:v;
}
void work(){
	scanf("%d %d",&n,&o);
	for(int i=0;i<n;i++)scanf("%lf %lf",x+i,y+i);
	memset(dp,0x3f,sizeof(dp));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			line[i][j]=0;
			if(i==j)line[i][j]|=(1<<j);
			else{
				double w=(x[i]*x[i])/(x[i]*x[i]+x[j]*x[j]);
				double b=(y[i]-w*y[i]-w*y[j])/(x[i]-w*x[i]-w*x[j]);
				double a=(y[i]-b*x[i])/(x[i]*x[i]);
				if(a>0)continue;
				if(fabs(a)<eps)continue;
				for(int k=0;k<n;k++){
					if(fabs(y[k]-a*x[k]*x[k]-b*x[k])<eps){
						line[i][j]|=(1<<k);
					}
				}
			}
		}
	}
	dp[0]=0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			for(int k=0,S;k<n;k++){
				S=(i|line[k][j]);
				dp[S]=min(dp[S],dp[i]+1);
			}
		}
	}
	printf("%d\n",dp[(1<<n)-1]);
	return;
}
int main(){
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	scanf("%d",&T);
	while(T--)work();
	return 0;
}