RT,可能被卡精度了

$O(Tn^22^n)$ 的算法

输入数据

答案

8
7
8
7
8

输出

8
8
9
8
9

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const double eps=1e-8;
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=18;
int T,n,m;
struct E{
	double x,y;
}e[MAX];
double a,b,c;
inline void chc(double &x,double &y,E i,E j){
	c=j.x*j.x*i.x-i.x*i.x*j.x;
	x=(j.y*i.x-i.y*j.x)/c;
	y=(i.y*j.x*j.x-j.y*i.x*i.x)/c;
}
int N,g[MAX+1][MAX+1],f[1<<MAX];
inline double abss(double x){
	return x<0?-x:x;
}
inline void solve(){
	memset(f,0x3f,sizeof(f));
	memset(g,0,sizeof(g));
	n=read(),m=read();N=1<<n;
	for(register int i=1;i<=n;++i)scanf("%lf %lf",&e[i].x,&e[i].y);
	for(register int i=1;i<n;++i){
		for(register int j=i+1;j<=n;++j){
			chc(a,b,e[i],e[j]);
			if(a<=-eps)
			for(register int k=1;k<=n;++k)if(abss((double)(e[k].x*e[k].x*a+e[k].x*b-e[k].y))<eps)g[i][j]|=(1<<(k-1));
		}
	}
	f[0]=0;
	for(register int S=0;S<N;++S){
		for(register int i=1;i<=n;++i){
			if(S&(1<<(i-1)))continue;
			f[S|(1<<(i-1))]=min(f[S|(1<<(i-1))],f[S]+1);
		}
		for(register int i=1;i<n;++i){
			if(S&(1<<(i-1)))continue;
			for(register int j=i+1;j<=n;++j){
				if(S&(1<<(j-1)))continue;
				f[S|g[i][j]]=min(f[S|g[i][j]],f[S]+1);				
			}
		}
	}
	printf("%d\n",f[N-1]);
}
signed main(){
//	freopen("in.in","r",stdin);
	T=read();
	while(T--)solve();
	return 0;
}