记录编号	474429	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	1.238 s
提交时间	2017-11-09 23:50:58	内存使用	2.83 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define eps (1e-8)
using namespace std;
inline char jud(long double t,long double r);
int t,n,m;
int dp[101][101],ans[1<<20];
long double x[101],y[101];
int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		memset(dp,0,sizeof(dp));
		memset(ans,127,sizeof(ans));
		for(int i=0;i<n;i++)cin>>x[i]>>y[i];
		long double a,b;
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
			{
				a=(x[j]*y[i]-x[i]*y[j])/(x[j]*x[i]*(x[i]-x[j]));
				b=(y[i]-a*x[i]*x[i])/x[i];
				if(~jud(a,0))continue;
				for(int k=0;k<n;k++)
					if(!jud(a*x[k]*x[k]+b*x[k],y[k]))
						dp[i][j]|=(1<<k);
			}
		ans[0]=0;
		for(int i=0;i < (1<<n);i++)
		{
			int k=__builtin_ctz(~i);
			ans[i|(1<<k)]=min(ans[i|(1<<k)],ans[i]+1);
			for(int j=k+1;j<n;j++)
				ans[i|dp[k][j]]=min(ans[i|dp[k][j]],ans[i]+1);
		}
		cout<<ans[(1<<n)-1]<<'\n';
	}
}
inline char jud(long double t,long double r)
{
	return abs(t-r) < eps ? 0 : (t<r ? -1 : 1);
}