题意描述
AC代码
代码语言：javascript
复制#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x )
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=25;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9 7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int n,m,f[M],path[N][N];
PDD q[N];
int cmp(double x,double y){
if(abs(x-y)<=eps) return 0;
if(x<y) return -1;
return 1;
}
void solve(){
cin>>n>>m;
rep(i,0,n) cin>>q[i].fi>>q[i].se;
mst(path,0);
rep(i,0,n){
path[i][i]=1<<i;
rep(j,0,n){
double x1=q[i].fi,y1=q[i].se;
double x2=q[j].fi,y2=q[j].se;
if(!cmp(x1,x2)) continue;
double a=(y1/x1-y2/x2)/(x1-x2);
if(a>=0) continue;
double b=y1/x1-a*x1;
int state=0;
rep(k,0,n){
double x=q[k].fi,y=q[k].se;
if(!cmp(a*x*x b*x,y)) state =1<<k;
}
path[i][j]=state;
}
}
mst(f,INF);
f[0]=0;
rep(i,0,(1<<n)-1){
int x=0;
rep(j,0,n){
if(!((i>>j)&1)){
x=j;
break;
}
}
rep(j,0,n){
f[i | path[x][j]]=min(f[i | path[x][j]],f[i] 1);
}
}
cout<<f[(1<<n)-1]<<endl;
}
int main(){
IOS;
//freopen("try.in", "r", stdin);
//freopen("try2.out", "w", stdout);
int t;cin>>t;
while(t--)
solve();
return 0;
}
