比赛 EYOI与SBOI开学欢乐赛7th 评测结果 WAAAATTTTW
题目名称 聪明的猴子 最终得分 40
用户昵称 什么都想学什么都学了一点的晓无痕 运行时间 4.879 s
代码语言 C++ 内存使用 6.31 MiB
提交时间 2022-09-23 20:22:09
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int M,N;
int m[501];
int x[1001]={0};
int y[1001]={0};
int save[1001]={0};
int f[1001][1001];
bool vis[1001][1001]={0};
int ans;
void dfs(int cnt,int lc)
{
    if(save[cnt]==N)
    {
        ++ans;
    }
        for(int j=1;j<=N;++j)
        {
            if(vis[cnt][j]==0&&m[cnt]>=f[lc][j])
            {
                   vis[cnt][j]=1;
                   save[cnt]++;
                  dfs(cnt,j);
            }
        }
}
int main()
{
    freopen("monkey.in","r",stdin);
    freopen("monkey.out","w",stdout);
    scanf("%d",&M);
    for(int i=1;i<=M;++i)
    {
        scanf("%d",&m[i]);
        m[i]=m[i]*m[i];
    }
    scanf("%d",&N);
    x[0]=0;y[0]=0;
    for(int i=1;i<=N;++i)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    for(int i=0;i<=N;++i)
    {
        for(int j=i+1;j<=N;++j)
        {
            if(j==i)
            continue;
            else
            {
             int mint=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
             f[i][j]=mint;
             f[j][i]=mint;
            }
        }
    }
    sort(m+1,m+M+1);
    ans=0;
    for(int i=1;i<=M;++i)
    {
        dfs(i,0);
    }
    printf("%d",ans);
    return 0;
}