Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

纪念1AC 萌新水过

Posted by 18477329 at 2020-10-16 19:32:50 on Problem 2236
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX_N 1005

int par[MAX_N]; //父节点
int rank[MAX_N]; //树的深度 
int n,d;
typedef pair<int,int> P;
P map[MAX_N];
int used[MAX_N];
int num=0;

void init()
{
	for(int i=0;i<n;i++)
	{
		par[i]=i;
		rank[i]=0;
	 } 
}

int find(int x)
{
	if(par[x]==x)
		return x;
	else
		return par[x]=find(par[x]);
}

bool same(int x,int y)
{
	return find(x)==find(y);
}

void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(rank[x]<rank[y])
		par[x]=y;
	else
	{
		par[y]=x;
		if(rank[x]==rank[y]) rank[x]++;
	}
}


void fun(int t)  //判断要不要加入并查集 
{
	for(int i=0;i<num-1;i++) //最后一个是自己 
	{
	    double ans;
	    int x1=map[used[i]].first,x2=map[t].first;
	    int y1=map[used[i]].second,y2=map[t].second;
	    ans=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
		if(ans<=d)
		{
			unite(t,used[i]);
		}
	}
}

void solve()
{
	int s,t;
	char c;
	init();
	fill(used,used+n,0);
	while(cin>>c)
	{
		if(c=='O')
		{
			cin>>t;
			used[num]=t;
			num++;
			fun(t);
		}
		if(c=='S')
		{
			cin>>s>>t;
			if(same(s,t))
				cout<<"SUCCESS"<<endl;
			else
				cout<<"FAIL"<<endl;
		}
	}
	return ;
}

int main()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		cin>>map[i].first>>map[i].second;
	}
	solve();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator