求助大佬,85分,RE了三个点,QAQ

回复帖子

@小梁 2019-01-29 10:26 回复

#include<algorithm>
#include<iostream>
#include<cstring>
#define N 19 
#define M 1<<19 
#define inf 0x3f 
#define eps 1e-8
#define LL long long
using namespace std;
int T,n,m,f[N][N],dp[M],k[M],p;
double x[N],y[N],a,b;
double abss(double xx) {return xx>0 ?xx :-xx;}
int maxx(int pp,int qq){return pp>qq ?pp :qq;}
int minn(int pp,int qq){return pp<qq ?pp :qq;}
int main()
{
    for (int i=0;i<(1<<18);i++)
        for (int j=1;j<=18;j++)
            if (!(i&(1<<(j-1)))) {k[i]=j;break; }   
    scanf("%d",&T);
    while (T--)
    {
        memset(f,0,sizeof(f));
        memset(dp,inf,sizeof(dp)); 
        dp[0]=0;
        scanf("%d%d",&n,&m);
        m=1<<n;
        for (int i=1;i<=n;i++)
            scanf("%lf%lf",&x[i],&y[i]);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            { 
                if (abss(x[i]-x[j])<eps) continue;
                b=(x[i]*x[i]*y[j]-x[j]*x[j]*y[i])/(x[i]*x[j]*(x[i]-x[j]));
                a=(y[i]-x[i]*b)/(x[i]*x[i]);  
                if (a>-eps) continue;
                for (int l=1;l<=n;l++)
                    if (abss(y[l]-a*x[l]*x[l]-b*x[l])<eps) f[i][j]|=(1<<(l-1));
            }
        for (int i=0;i<m;i++)
        {
            int p=k[i];
            dp[i|(1<<(p-1))]=minn(dp[i|(1<<(p-1))],dp[i]+1);
            for (int j=1;j<=n;j++)
                dp[i|f[p][j]]=minn(dp[i|f[p][j]],dp[i]+1);
        }
        printf("%d\n",dp[m-1]);
    }
    return 0;
}```
@AThousandSuns 2019-01-29 10:42 回复 举报

@小梁 作为写题解的蒟蒻来回答一下……您试着把N和M改成 $20$ 和 $1<<20$ 试一下……我现在去改题解……

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。