80分求助
查看原帖
80分求助
555937
programmer400楼主2022/7/20 15:54

6 8WA

#include<iostream>
#include<vector>
#define db(n) cout<<n;system("pause");
using namespace std;
struct Point
{
	int x,y,md;
	bool vis;
};
int dissq(const Point&a,const Point&b)//距离平方 
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main()
{
	int m;
	cin>>m;
	vector<int>s(m);
	for(auto&i:s)
	{
		cin>>i;
		i*=i;//避免后面开方 
	}
	int n;
	cin>>n;
	vector<Point>mp(n);
	for(auto& i:mp)
	{
		cin>>i.x>>i.y;
		i.md=dissq(i,mp[0]);
		i.vis=false;
	}
	//prim算法 
	int maxs=0;//最小瓶颈生成树最大边权 
	int cnt=0;
	while(cnt<n-1)
	{
		int minn=0;
		int mind=1000000000;
		for(int i=0;i<n;i++)//找出距离最近的点 
		{
			if(!mp[i].vis&&mp[i].md<mind)
			{
				minn=i;
				mind=mp[i].md;
			}
		}
		mp[minn].vis=true;
		if(mp[minn].md>maxs)
			maxs=mp[minn].md;
		for(auto& i:mp)
		{
			i.md=min(i.md,dissq(mp[minn],i));
		}
		cnt++;
	}
	int ans=0;
	for(auto&i:s)
	{
		if(i>=maxs)
			ans++;
	}
	cout<<ans;
	return 0;
}
2022/7/20 15:54
加载中...