比赛 |
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;
}