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

1A的,咱也贴次代码

Posted by 806601756 at 2012-02-18 16:14:45 on Problem 2236
#include <stdio.h>
#include <math.h>
#include <string.h>
#define M 1010

struct In{
	int x, y;
}pos[M];
double map[M][M];
int con[M][M], p[M], v[M];

void Creat(int n)
{
	int i;
	for (i = 1; i <= n; i++)
		p[i] = i;
}

int Find(int x)
{
	if (x != p[x])
		return p[x] = Find(p[x]);
	return x;
}

void Union(int a, int b)
{
	int pa, pb;
	pa = Find(a);
	pb = Find(b);
	p[pa] = pb;
}

int main()
{
	int n, d, i, j, a, b, pa, pb;
	char s[5];
	while ((scanf("%d%d", &n, &d)) != EOF)
	{
		Creat(n);
		for (i = 1; i <= n; i++)
			scanf("%d%d", &pos[i].x, &pos[i].y);
		memset(con, 0, sizeof(con));
		memset(v, 0 , sizeof(v));
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
			{
				map[i][j] = map[j][i] = sqrt((pos[i].x - pos[j].x)*(pos[i].x - pos[j].x)*1.0 + (pos[i].y - pos[j].y)*(pos[i].y - pos[j].y)*1.0);
				if (map[i][j] < d + 0.00000001)
					con[i][j] = con[j][i] = 1;
			}
		while ((scanf("%s", s)) != EOF)
		{
			if (s[0] == 'O')
			{
				scanf("%d", &a);
				v[a] = 1;
				for (i = 1; i <= n; i++)
				{
					if (i == a) continue;
					if (con[i][a] == 1 && v[i] == 1)
					{
						Union(i, a);
					}
				}
			}
			if (s[0] == 'S')
			{
				scanf("%d%d", &a, &b);
				pa = Find(a);
				pb = Find(b);
				if (pa == pb) printf("SUCCESS\n");
				else printf("FAIL\n");
			}
		}
	}
	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