刚才ABC,DWA11个点,求调
  • 板块学术版
  • 楼主wangshi
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/9 22:18
  • 上次更新2023/10/27 21:18:10
查看原帖
刚才ABC,DWA11个点,求调
541553
wangshi楼主2022/7/9 22:18
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6,M=1e6+10;
ll n,x[N],y[N],r[N],sx,sy,tx,ty,head[M],cnt,q,z,vis[N];
struct edge
{
	int to,next;
}e[M];
bool check(ll x1,ll y1,ll x2,ll y2,ll r1,ll r2)
{
	long double len=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	if(len>(r1+r2)*(r1+r2)||len<(r1-r2)*(r1-r2)) return 0;
	else return 1;
}
bool check2(ll a,ll b,ll r,ll x,ll y)
{
	long double m,n;
	m=pow(x-a,2),n=pow(y-b,2);
	if(m+n==r*r) return 1;
	else return 0;
}
void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
bool dfs(int u)
{
	if(u==z) return 1;
	vis[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]) continue;
		if(dfs(v)) return 1;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>sx>>sy>>tx>>ty;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>r[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(check(x[i],y[i],x[j],y[j],r[i],r[j]))
			{
				add(i,j);
				add(j,i);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(check2(x[i],y[i],r[i],sx,sy)) q=i;
		if(check2(x[i],y[i],r[i],tx,ty)) z=i;
	}
	if(dfs(q)) cout<<"Yes";
	else cout<<"No";
	return 0;
}

好像已经跟官方的题解差不多了,不知道那错了

2022/7/9 22:18
加载中...