记录编号	608864	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	6.761 s
提交时间	2025-10-29 21:34:59	内存使用	7.88 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=20;
const double eps=1e-6;
int n,_;
struct node{
	double x,y;
}s[N];
bool cmp(node a,node b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
int f[1<<N];
map<pair<double,double>,int> m;
void init(){
	int zanshi;
	scanf("%d%d",&n,&zanshi);
	for(int i=0;i<n;i++) scanf("%lf%lf",&s[i].x,&s[i].y);
	sort(s,s+n,cmp);
	m.clear();
	memset(f,0x3f,sizeof(f));
	return;
}
void work(double &a,double &b,double xa,double ya,double xb,double yb) {
	a=(ya*xb-yb*xa)/(xb*xa*xa-xa*xb*xb);
	b=(ya-a*xa*xa)/xa;
	return;
}
void solve(){
	double xa,ya,xb,yb,a,b,fc;
	int mk;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			xa=s[i].x;ya=s[i].y;
			xb=s[j].x;yb=s[j].y;
			if(fabs(xa-xb)<eps) continue;
			work(a,b,xa,ya,xb,yb);
			if(a>-eps) continue;
			if(m.find({a,b})==m.end()){
				mk=0;
				for(int k=0;k<n;k++){
					fc=a*s[k].x*s[k].x+b*s[k].x;
					if(fabs(fc-s[k].y)<eps) mk|=(1<<k);
				}
				m[{a,b}]=mk;
			}
		}
	}
	return;
}
void DP(){
	for(int i=0;i<n;i++) m[{i,0}]=(1<<i);
	f[0]=0;
	for(int i=0;i<(1<<n);i++){
		if(f[i]==0x3f3f3f) continue;
		for(auto it:m) f[i|it.second]=min(f[i|it.second],f[i]+1);
	}
	printf("%d\n",f[(1<<n)-1]);
	return;
}
int main(){
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	scanf("%d",&_);
	while(_--){
		init();
		solve();
		DP();
	}
	return 0; 
}