记录编号	608823	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.869 s
提交时间	2025-10-29 20:03:18	内存使用	20.22 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double 
ll T;
ll n,m,pwx[20][20],lbit[1100000],f[1100000]; 
db x[20],y[20];
int main(){
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);
	for(int i=0;i<(1<<20);i++){
		int j=1;
		while (j<=18&&(i&(1<<(j-1)))) j++;lbit[i]=j;
	}
	cin>>T;
	while(T--){
		memset(pwx,0,sizeof(pwx));
		memset(f,0x3f,sizeof(f));
		f[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])<1e-8) continue;
				db a,b;
				b=(x[i]*x[i]*y[j]-x[j]*x[j]*y[i])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
				a=(y[i]-x[i]*b)/x[i]/x[i];
				if(a>-1e-8) continue;
				for(int k=1;k<=n;k++){
					if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<1e-8){
						pwx[i][j]|=(1<<(k-1));
					}
				}
			}
		}
		for(int i=0;i<(1<<n);i++){
			int j=lbit[i];
			f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
			for(int k=1;k<=n;k++) f[i|pwx[j][k]]=min(f[i|pwx[j][k]],f[i]+1);
		}
		cout<<f[(1<<n)-1]<<endl;
	}
	return 0;
}