记录编号	356166	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	2.207 s
提交时间	2016-11-29 19:42:08	内存使用	1.32 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define CK 1e-6
using namespace std;

int t,n,m,i;
int v[25],z[25],zt[2020];
double x[25],y[25];
int f[262199];

double Abs(double x){return (x<0)?-x:x;}

int min(int a,int b){return (a<b)?a:b;}

void Ready(){
	int i=0,j=0,g=0,s=0;
	double c1=0,c2=0;
	z[1]=1;	memset(f,0x3f3f3f3f,sizeof(f));	memset(zt,0,sizeof(zt));
	if (m==1)	f[(1<<n)-1]=(n/3)+1;	else f[(1<<n)-1]=n;
	for (i=2;i<=n;i++) z[i]=z[i-1]*2;
	for (i=1;i<=n;i++)	zt[++zt[0]]=z[i];
	for (i=1;i<=n-1;i++)
		for (j=i+1;j<=n;j++){
			memset(v,0,sizeof(v));	s=0;
			if (x[i]==x[j])	continue;
			if (Abs(x[i]/y[i]-x[j]/y[j])<CK)	continue;
			c1=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[i]*x[j]-x[i]*x[j]*x[j]*1.0)*1.0;
			c2=(y[i]-c1*x[i]*x[i])/(x[i]*1.0);
			if (c1>0)	continue;
			for (g=1;g<=n;g++) if (Abs(x[g]*x[g]*c1*1.0+c2*x[g]*1.0-y[g]*1.0)<CK)
				if (g<i)	break;	else s+=z[g];
			f[s]=1;	zt[++zt[0]]=s;
 		}
 	for (i=1;i<=n;i++)	f[z[i]]=1;
}

void Work(){
	int i=0,j=0;
	for (i=0;i<=(1<<n)-1;i++)
		for (j=1;j<=zt[0];j++)
			if (i!=zt[j]) f[i|zt[j]]=min(f[i|zt[j]],f[i]+f[zt[j]]);
	printf("%d\n",f[(1<<n)-1]);
}

int main(){
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	scanf("%d",&t);
	while (t--){
		memset(f,0,sizeof(f));
		scanf("%d%d",&n,&m);
		for (i=1;i<=n;i++)	scanf("%lf%lf",&x[i],&y[i]);
		Ready();	Work();
	}
	return 0;
}