思路来自于题解 甚至可以说代码很像…… AC：（题解中的转移方式）

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const double eps=1e-8;
int n,m,dp[1<<20],T,state[20][20];
double x[20],y[20],a,b;
void calc(int i,int j,double &a,double &b)
{
	a=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[j]*(x[i]-x[j]));
	b=(y[j]*x[i]*x[i]-y[i]*x[j]*x[j])/(x[i]*x[j]*(x[i]-x[j]));
}
int main()
{
	//freopen("P2831_1.in","r",stdin);
	scanf("%d",&T);
	for (int F=1;F<=T;F++)
	{
		scanf("%d%d",&n,&m);
		for (int i=0;i<n;i++)
			scanf("%lf%lf",&x[i],&y[i]);
		memset(state,0,sizeof(state));
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
				if (i==j) continue;
				if (abs(x[i]-x[j])<=eps) continue;
				calc(i,j,a,b);
				if(a>-eps) continue; 
				for (int k=0;k<n;k++)
				{
					if (abs(a*x[k]*x[k]+b*x[k]-y[k])<=eps)
						state[i][j]|=(1<<k);
				}
			}
		}
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for (int i=0;i<(1<<n);i++)
		{
			for (int j=0;j<n;j++)
			{
				if (i&(1<<j)) continue;
				dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+1);
				for (int k=0;k<n;k++)
				{
					dp[i|state[j][k]]=min(dp[i|state[j][k]],dp[i]+1);
				}
			}
		}
		printf("%d\n",dp[(1<<n)-1]);
	}
	return 0;
} 

WA ON #8:个人认为这种转移想起来更加自然，当然实质上是一样的

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const double eps=1e-9;
int n,m,dp[1<<20],T,state[20][20];
double x[20],y[20],a,b;
void calc(int i,int j,double &a,double &b)
{
	a=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[j]*(x[i]-x[j]));
	b=(y[j]*x[i]*x[i]-y[i]*x[j]*x[j])/(x[i]*x[j]*(x[i]-x[j]));
}
int main()
{
	//freopen("P2831_1.in","r",stdin);
	scanf("%d",&T);
	for (int F=1;F<=T;F++)
	{
		scanf("%d%d",&n,&m);
		for (int i=0;i<n;i++)
			scanf("%lf%lf",&x[i],&y[i]);
		memset(state,0,sizeof(state));
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
				if (i==j) continue;
				if (abs(x[i]-x[j])<=eps) continue;
				calc(i,j,a,b);
				if(a>-eps) continue; 
				for (int k=0;k<n;k++)
				{
					if (abs(a*x[k]*x[k]+b*x[k]-y[k])<=eps)
						state[i][j]|=(1<<k);
				}
			}
		}
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for (int i=1;i<(1<<n);i++)
		{
			for (int j=0;j<n;j++)
			{
				if (i&(1<<j))
				{
					dp[i]=min(dp[i^(1<<j)]+1,dp[i]);
					for (int k=0;k<n;k++)
					{
						if ((i|state[j][k])==i) dp[i]=min(dp[i^state[j][k]]+1,dp[i]);
					}
				}
			}
		}
		printf("%d\n",dp[(1<<n)-1]);
	}
	return 0;
}