记录编号	467425	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	BFZD	是否通过	通过
代码语言	C++	运行时间	5.080 s
提交时间	2017-10-30 16:43:10	内存使用	11.76 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=1000000+10;
double eps=1e-6;
int weapen[maxn];
int cnt;
int p[maxn];
struct node
{
	double x,y;
}a[50+10];
int t,n,m;
double b,c;
void work(int i,int j);
bool can(int x);
int f[maxn];
int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(weapen,0,sizeof(weapen));
		memset(p,false,sizeof(p));
		for(int i=1; i<=n; i++)
		{
			scanf("%lf%lf",&a[i].x,&a[i].y);
		}
		for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
		{
	 		work(i,j);
	 		if(fabs(b)<=eps || b>eps) continue;
	 		int tmpp=0;
	 		for(int k=1; k<=n; k++)
	 		{
	 			if(can(k))
	 			{
	 				tmpp|=1<<(k-1);
	 			}
	 		}
	 		if(!p[tmpp])
	 		{
	 			p[tmpp]=1; cnt++; weapen[cnt]=tmpp;
	 		}
		}
		for(int i=1; i<=n; i++)
		{
			int tmpp=1<<(i-1);
			if(!p[tmpp])
			{
				p[tmpp]=1;
				cnt++; weapen[cnt]=tmpp;
			}
		}
		memset(f,60,sizeof(f));
		f[0]=0;
		for(int i=0; i<=(1<<n); i++)
		{
			for(int j=1; j<=cnt; j++)
			{
				f[i|weapen[j]]=min(f[i]+1,f[i|weapen[j]]);
			}
		}
		cout<<f[(1<<n)-1]<<endl;
	}
	return 0;
}
void work(int i,int j)
{
	b=(a[j].y-a[i].y*(a[j].x/a[i].x))/(a[j].x*a[j].x-a[i].x*a[j].x);
	c=(a[j].y-(a[i].y*((a[j].x*a[j].x)/(a[i].x*a[i].x))))/(a[j].x-a[j].x*a[j].x/a[i].x);
}
bool can(int x)
{
	double tmp=a[x].x*a[x].x*b+c*a[x].x;
	if(fabs(tmp-a[x].y)<=eps) return true;
	return false;
}
//angrybirds