记录编号	608809	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	梧叶已同秋雨去	是否通过	通过
代码语言	C++	运行时间	6.126 s
提交时间	2025-10-29 15:37:28	内存使用	4.15 MiB

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
double kkf=1e-8;
bool den(double a,double b){
	return fabs(a-b)<kkf;
}
struct node{
	double x,y;
}zhu[25];
double powa(node a,node b){
	double a1=a.x*a.x,b1=a.x;
	double a2=b.x*b.x,b2=b.x;
	if(!(a2-(b2/b1)*a1)){
		return 1.0;
	}
	return (b.y-(a.y*(b2/b1)))/(a2-(b2/b1)*a1);
}
double powb(node a,node b,double c){
	return (a.y-c*a.x*a.x)/a.x;
}
long long li[25][25],dp[300005];
int main(){
//	freopen("angrybirds.in","r",stdin);
//	freopen("angrybirds.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>zhu[i].x>>zhu[i].y;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				li[i][j]=0;
			}
		} 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j)continue;
				double a=powa(zhu[i],zhu[j]);
				double b=powb(zhu[i],zhu[j],a);
				if(a>0||den(a,0))continue;
				li[i][j]=li[i][j]|(1<<(i-1));
				li[i][j]=li[i][j]|(1<<(j-1));
				for(int k=1;k<=n;k++){
					if(k==i||k==j)continue;
					if(den(a*zhu[k].x*zhu[k].x+b*zhu[k].x,zhu[k].y)){
						li[i][j]=li[i][j]|(1<<(k-1));
					}
				}
			}
		}
		for(int i=0;i<=(1<<n)-1;i++){
			dp[i]=1e9;
		}
		dp[0]=0;
		for(int k=0;k<=(1<<n)-1;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					dp[k|li[i][j]]=min(dp[k|li[i][j]],dp[k]+1);
					dp[k|(1<<(j-1))]=min(dp[k|(1<<(j-1))],dp[k]+1);	
				}
			}
		}
		cout<<dp[(1<<n)-1]<<"\n";
	}
	return 0;
}