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

之前想的太复杂了 贴上AC代码

Posted by Buffoon_fish at 2009-03-17 11:30:20 on Problem 2236
#include<stdio.h>
#include<math.h>
#include<string>
#include<memory>
using namespace std;

int fa[1001+5];
int closet[1001+5];

int getfa(int t)
{
	if(t == fa[t])
		return t;
	fa[t] = getfa(fa[t]);
	return fa[t];
}
typedef struct node
{
	int x;
	int y;
}Node;
Node arry[1001+5];

double cal(Node a,Node b)
{
	double d;
	d = (a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y);
	d = sqrt(d);
	return d;
}

int main()
{
	int n;// number of computers
	int maxd;// the maximum distance two computers can communicate directly
	int i,j;
	char op[5];
	int c1,c2;
	double temp;


	for(i=0;i<1006;i++)
		fa[i] = i;
	memset(closet,0,sizeof(closet));
	scanf("%d%d",&n,&maxd);


	for(i=1;i<=n;i++)
		scanf("%d%d",&arry[i].x,&arry[i].y);

	while(scanf("%s",op) != EOF)
	{
		if(strcmp(op,"O") == 0)
		{
			scanf("%d",&c1);
			closet[c1] = 1;
		
			for(j=1;j<=n;j++)
			{
				if(closet[j])
				{
					temp = cal(arry[c1],arry[j]);
					if((temp <= maxd) && (getfa(c1) != getfa(j)))
						fa[getfa(c1)] = getfa(j);

				}
			}
						
		}
		else if(strcmp(op,"S") == 0)
		{
			scanf("%d%d",&c1,&c2);
			if(getfa(c1) == getfa(c2))
				printf("SUCCESS\n");
			else
				printf("FAIL\n");
		}
	}
	return 1;
}

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