搜索基础

EndSaH的

#include
    
     using namespace std;const int MAXN=20;const double eps=1e-6;struct Point{    double x,y;}p[MAXN],surp[MAXN];struct Para{    double a,b;}par[MAXN];int T,n,m,ans;inline bool equal(double x,double y){    return x-y>=-eps&&x-y<=eps;}inline bool inc(double a,double b,double x,double y){    return equal(a*x*x+b*x,y);}inline void build(double &a,double &b,double x1,double y1,double x2,double y2){    a=(x2*y1-x1*y2)/(x1*x2*(x1-x2));    b=(x1*x1*y2-x2*x2*y1)/(x1*x2*(x1-x2));//矩阵乘法+逆矩阵求法 }inline void dfs(int now,int num,int rest){//DFS最重要的是分清楚情况     if(num+rest>=ans) return;    if(now>n){        ans=num+rest;        return;    }    for(int i=1;i<=num;i++){        if(inc(par[i].a,par[i].b,p[now].x,p[now].y)){            dfs(now+1,num,rest);//此点已被覆盖             return;        }    }    for(int i=1;i<=rest;i++){        if(equal(p[i].x,p[now].x)) continue;        double a,b;        build(a,b,surp[i].x,surp[i].y,p[now].x,p[now].y);//组成新抛物线         if(a<0){            par[num+1]=(Para){a,b};            Point tmp=surp[i];            for(int j=i;j<=rest-1;j++)                surp[j]=surp[j+1];            dfs(now+1,num+1,rest-1);            for(int j=rest;j>=i+1;j--)                surp[j]=surp[j-1];            surp[i]=tmp;        }    }    surp[rest+1]=p[now];//不与任何点组成新抛物线     dfs(now+1,num,rest+1);}int main(){    scanf("%d",&T);    while(T--){        ans=1e9;        scanf("%d%d",&n,&m);        for(int i=1;i<=n;i++){            scanf("%lf%lf",&p[i].x,&p[i].y);        }        dfs(1,0,0);        printf("%d\n",ans);    }}
    

\(DP\)做法

#include
    
     using namespace std;const int INF=1e8;double x[20],y[20];int para[200],dp[1<<18];int n,m,countpara;int Min(int x,int y){return x
     
      =-1e-6&&t<=1e-6;//精度判断 }void pre(){    scanf("%d%d",&n,&m);    for(int i=0;i<(1<
      
       =0) continue;            para[countpara]=(1<