whyWA8
查看原帖
whyWA8
1392543
_X_Z_N_楼主2025/1/18 20:30
#include<bits/stdc++.h>
using namespace std;
float e[1005][1005];
int mon[505];
int xx[1005];
int yy[1005];
int n,m;
float dis[1005];
bool book[1005];
float mx=0;
int main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>mon[i];
    }
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>xx[i];
        cin>>yy[i];
        dis[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                e[i][j]=sqrt((xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j]));
            }
        }
    }
    //-----------------------
    dis[1]=0;
    book[1]=0;
    for(int i=2;i<=n;i++)
    {
        dis[i]=min(e[1][i],dis[i]);
    }
    for(int i=2;i<=n;i++)
    {
        int t=0x3f3f3f3f;
        int r=-1;
        for(int j=2;j<=n;j++)
        {
            if(!book[j] && dis[j]<t)
            {
                t=dis[j];
                r=j;
            }
        }
        if(r==-1)
        {
            break;
        }
        book[r]=1;
        for(int j=2;j<=n;j++)
        {
            dis[j]=min(dis[j],e[r][j]);
            mx=max(mx,dis[j]);
        }
    }
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        if(mon[i]>=mx)
        {
            sum++;
        }
    }
    cout<<sum;
    return 0;
}
2025/1/18 20:30
加载中...