2356170_tle.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 77 行

#include <stdio.h>
#include <string.h>

int m, d;
struct node
{
	int num;
	int adj[1002];
	int id;
	int x, y;
}pot[1002];
int mended[1003];

int dis(int i,int j)
{
	return (pot[i].x-pot[j].x)*(pot[i].x-pot[j].x)+(pot[i].y-pot[j].y)*(pot[i].y-pot[j].y);
}

int main()
{
	int i, j;
	int a, b;
	int t1, t2;
	char com[2];

	scanf("%d%d",&m,&d);
	memset(mended,0,sizeof(mended));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&pot[i].x,&pot[i].y);
		pot[i].id = i;
		pot[i].num = 0;
	}
	for(i = 0; i < m-1; i++)
	{
		for(j = i+1; j < m; j++)
		{
			if(dis(i,j)<=d*d)
			{
				pot[i].adj[pot[i].num++] = j;
				pot[j].adj[pot[j].num++] = i;
			}
		}
	}
	while(scanf("%s",com)==1)
	{
		if(com[0]=='S')
		{
			scanf("%d%d",&a,&b);
			a--,b--;
			if(pot[a].id==pot[b].id)
				printf("SUCCESS\n");
			else
				printf("FAIL\n");
		}
		else
		{
			scanf("%d",&a);
			a--;
			if(mended[a])
				continue;
			else
				mended[a] = 1;
			t2 = pot[a].id;
			for(i = 0; i < pot[a].num; i++)
			{
				t1 = pot[pot[a].adj[i]].id;
				if(!mended[pot[a].adj[i]])
					continue;
				for(j = 0; j < m; j++)
					if(pot[j].id==t1&&mended[j])
						pot[j].id = t2;
			}
		}
	}
	return 1;
}