题意描述

AC代码

#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;
}