记录编号	449347	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	2.321 s
提交时间	2017-09-14 08:05:06	内存使用	8.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const double eps=1e-6;
int n,m,t,pwx[20][20],f[1<<20],cnt[1<<20];
double x[20],y[20];

int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		memset(pwx,0,sizeof(pwx));
		memset(f,0x3f,sizeof(f));
		memset(cnt,0,sizeof(cnt));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
		for(int i=1;i<n;i++){
			for(int j=i+1;j<=n;j++){
				double a,b;
				a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
				b=(y[i]-a*x[i]*x[i])/x[i];
				if(a<-eps){
					for(int k=1;k<=n;k++){
						if(abs(y[k]-a*x[k]*x[k]-b*x[k])<=eps){
							pwx[i][j]|=(1<<(k-1));
						}
					}
				}
				
			}
		}
		for(int i=1;i<(1<<n);i++) cnt[i]=cnt[i>>1]+(i&1);
		f[0]=0;
		for(int i=0;i<(1<<n);i++){
			f[i]=min(f[i],cnt[i]);
			for(int j=1;j<n;j++){
				for(int k=j+1;k<=n;k++){
					f[i|pwx[j][k]]=min(f[i|pwx[j][k]],f[i]+1);
				}
			}
		}
		printf("%d\n",f[(1<<n)-1]);
	}
	return 0;
}