记录编号	419827	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	2.158 s
提交时间	2017-07-03 15:27:05	内存使用	4.32 MiB

#include<bits/stdc++.h>

using namespace std;

int T,n,m,f[1<<20],b[20][20],xian[450],cnt;
double a[20][2],p,q;

int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&T);
	while(T--)
	{
		cnt=0;
		memset(b,0,sizeof(0));
		memset(a,0,sizeof(0));
		memset(xian,0,sizeof(xian));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		scanf("%lf%lf",&a[i][0],&a[i][1]);
		for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(abs(a[i][0]-a[j][0])<1e-6)continue;//判断两头猪在同一条竖线上 
			if((a[i][1]/a[i][0]-a[j][1]/a[j][0])/(a[i][0]-a[j][0])>=-1e-6)//A斜率比B大，横坐标也比B靠后，那么他们构成不了抛物线 
			continue;
			q=(a[i][1]*a[j][0]-a[i][0]*a[j][1])/(a[i][0]*a[i][0]*a[j][0]-a[j][0]*a[j][0]*a[i][0]);
			p=(a[i][1]*a[j][0]*a[j][0]-a[j][1]*a[i][0]*a[i][0])/(a[i][0]*a[j][0]*a[j][0]-a[i][0]*a[i][0]*a[j][0]);
			xian[++cnt]|=1<<(i-1);
			xian[cnt]|=1<<(j-1);
			for(int k=1;k<=n;k++)
			{
				double g=q*a[k][0]+p;
				if(abs(g-a[k][1]/a[k][0])<1e-7)//神奇的卡精度蒟蒻表示只能照搬 
				xian[cnt]|=1<<(k-1);
			}
		}/*
		for(int i=1;i<=n;i++)
		{
			for(int j=i;j<=n;j++)
				cout<<b[i][j]<<" ";
			cout<<endl;
		}
		cout<<endl;*/
		int t=(1<<n)-1;
		memset(f,20,sizeof(f));
		f[0]=0;
		for(int i=1;i<=n;i++)
		xian[++cnt]|=1<<(i-1);
		for(int i=0;i<=t;i++)//这里从0开始，因为所有状态都是由0转移来的 
		{
			for(int k=1;k<=cnt;k++)
			{
				f[xian[k]|i]=min(f[i|xian[k]],f[i]+1);//每一个xian【i】存的都是一条线打掉的猪的状态 
			}
		}
//		for(int i=1;i<=t;i++)
//		cout<<f[i]<<" ";
//		cout<<endl;
		cout<<f[t]<<endl;
	}
	return 0;
}