比赛 EYOI与SBOI开学欢乐赛7th 评测结果 AAAAAAAAAA
题目名称 聪明的猴子 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.386 s
代码语言 C++ 内存使用 3.45 MiB
提交时间 2022-09-23 19:25:42
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1000+5;
int n,m;
int s[N],x[N],y[N];
queue<int>q;
bool vis[N]={0};
int sq(int t){
    return t*t;
}
bool yes(int u,int v,int d){
    if (sq(x[u]-x[v])+sq(y[u]-y[v])<=d*d)return 0;
    return 1;
}
bool check(int d){
    memset(vis,0,sizeof(vis));
    while(!q.empty())q.pop();
    q.push(1);vis[1]=1;int cnt=1;
    while(!q.empty()){
        int t=q.front();q.pop();
        for (int i=1;i<=n;i++){
            if (vis[i]||yes(t,i,d))continue;
            q.push(i);vis[i]=1;cnt++;
            if (cnt==n)return 0;
        }
    }
    return 1;
}
int main(){
	freopen ("monkey.in","r",stdin);
	freopen ("monkey.out","w",stdout);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)scanf("%d",&s[i]);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    int l=1,r=1000;
    while(l<r){
        int mid=(l+r)/2;
        if (check(mid))l=mid+1;
        else r=mid;
    }
    int ans=0;
    for (int i=1;i<=m;i++)if (s[i]>=l)ans++;
    printf("%d\n",ans);
    return 0;
}