比赛 EYOI与SBOI开学欢乐赛7th 评测结果 WWWWWWWWWA
题目名称 聪明的猴子 最终得分 10
用户昵称 Lesater 运行时间 0.294 s
代码语言 C++ 内存使用 8.04 MiB
提交时间 2022-09-23 20:50:19
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m;
#define P pair<int,int>
long long mky[501],far[1001],dthh[1001][1001],ans;
P mapp[1001];
long long dth(P a,P b,int c,int d)
{
    if(dthh[c][d]!=0) return dthh[c][d]; 
    dthh[c][d]=pow(a.first-b.first,2)+pow(a.second-b.second,2);    
    return dthh[c][d];
}
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    freopen("monkey.in","r",stdin);
    freopen("monkey.out","w",stdout);
    memset(far,0x3f,sizeof far);
    mapp[0].first=0; mapp[0].second=0;
    cin>>m;
    for(int i=1;i<=m;++i)
    cin>>mky[i];
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int a,b;
        cin>>a>>b;
        mapp[i].first=a; mapp[i].second=b;
        int k;
        for(int j=0;j<i;++j)
        {
            if(far[i]>dth(mapp[i],mapp[j],min(i,j),max(i,j)))
            {
            k=j;
            far[i]=dth(mapp[i],mapp[j],min(i,j),max(i,j));
            }
        }
        for(int j=1;j<i&&j!=k;++j)
            far[j]=min(far[j],dth(mapp[i],mapp[j],min(i,j),max(i,j)));
    }
    sort(far+1,far+1+n,cmp); ans=far[1];   
    int tle=0;
    for(int i=1;i<=m;++i)
       if(mky[i]*mky[i]>=ans) 
       tle++;
    cout<<tle;
    return 0;
}