题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=18,M=1<<N;
const double eps=1e-8;
int T;
int n,m;
typedef pair<double,double> pdd;
pdd q[N];
int path[N][N];
int f[M];
int cmp(double x,double y)
{
    if(fabs(x-y)<eps) return 0;
    if(x<y) return -1;
    else return 1;
}
int main()
{
    cin>>T;
    while(T--)
    {
        memset(q,0,sizeof q);
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>q[i].x>>q[i].y;
        }
        memset(path,0,sizeof path);
        for(int i=0;i<n;i++)
        {
            path[i][i]=1<<i;
            for(int j=0;j<n;j++)
            {
                double x1=q[i].x,y1=q[i].y;
                double x2=q[j].x,y2=q[j].y;
                if(cmp(x1,x2)==0) continue;
                double a=(y1/x1-y2/x2)/(x1-x2);
                double b=y1/x1-a*x1;
                if(cmp(a,0)>=0) continue;
                int state=0;
                for(int k=0;k<n;k++)
                {
                    double x=q[k].x,y=q[k].y;
                    if(cmp(a*x*x+b*x,y)==0)
                       state+=1<<k;
                } 
                path[i][j]=state;
            }
        }
        memset(f,0x3f,sizeof f);
        f[0]=0;
        for(int i=0;i<1<<n;i++)
        {
            int x=0;
            for(int j=0;j<n;j++)
            {
                if((i>>j&1)==0)
                {
                    x=j;
                    break;
                }
            }
            for(int j=0;j<n;j++)
            {
                f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1);
            }
        } 
        cout<<f[(1<<n)-1]<<endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla