记录编号	367625	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.386 s
提交时间	2017-01-31 21:08:08	内存使用	1.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const double eps=1e-8;
bool allclose(double a,double b){
	return fabs(a-b)<eps;
}
const int SIZEN=20,INF=0x7fffffff/2;
int N,M;
double X[SIZEN],Y[SIZEN];
bool fit(double x1,double y1,double x2,double y2,double &a,double &b){
	//array([[x1^2,x1,y1],[x2^2,x2,y2]])
	//solve through Cramer's rule
	double D = x1*x1*x2-x2*x2*x1;
	if(D==0) return false;
	double D1 = y1*x2-y2*x1;
	double D2 = x1*x1*y2-x2*x2*y1;
	a=D1/D;
	b=D2/D;
	//cout<<a<<" "<<b<<endl;
	return a<-eps;
}
int on_trajectory(double a,double b,int k){
	return allclose(a*X[k]*X[k]+b*X[k],Y[k]);
}
int assess(int k1,int k2){
	double a,b;
	if(!fit(X[k1],Y[k1],X[k2],Y[k2],a,b)) return 0;
	int ret=0;
	for(int i=0;i<N;i++){
		if(on_trajectory(a,b,i)) ret|=(1<<i);
	}
	//cout<<ret<<endl;
	return ret;
}
vector<int> weapons;
int F[1<<18];
void work(void){
	weapons.clear();
	for(int i=0;i<N;i++) weapons.push_back(1<<i);
	for(int i=0;i<N;i++){
		for(int j=0;j<i;j++){
			int s = assess(i,j);
			if(s) weapons.push_back(s);
		}
	}
	for(int s=0;s<(1<<N);s++) F[s]=INF;
	F[0]=0;
	for(int s=0;s<(1<<N);s++){
		for(int k=0;k<weapons.size();k++){
			int d=weapons[k];
			F[s]=min(F[s],F[s-(s&d)]+1);
		}
	}
	printf("%d\n",F[(1<<N)-1]);
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++) scanf("%lf%lf",&X[i],&Y[i]);
}
int main(){
	//freopen("input.in","r",stdin);
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}
	return 0;
}