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

typedef struct{
	int x, y;
	char name[20];
} location;

int coord_x(int x1, int y1, int r1, int x2, int y2, int r2, int x3, int y3, int r3)
{
    int x;
    x = ((y2-y3)*(y2*y2-y1*y1+x2*x2-x1*x1+r1*r1-r2*r2)-(y1-y2)*(y3*y3-y2*y2+x3*x3-x2*x2+r2*r2-r3*r3))/(2*((x2-x1)*(y2-y3)-(x3-x2)*(y1-y2)));
    return x;
}
int coord_y(int x1, int y1, int r1, int x2, int y2, int r2, int x3, int y3, int r3)
{
    int y;
    y = ((x2-x3)*(x2*x2-x1*x1+y2*y2-y1*y1+r1*r1-r2*r2)-(x1-x2)*(x3*x3-x2*x2+y3*y3-y2*y2+r2*r2-r3*r3))/(2*((y2-y1)*(x2-x3)-(y3-y2)*(x1-x2)));
    return y;
}

int distance(location n1, location n2)
{
	return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
}

void rf(int ***a, int n)
{
    int i, j, k;
	for (k=1; k<=n; k++)
		for (i=1; i<=n; i++)
			for (j=1; j<=n; j++)
			{
				if ((*a)[i][j] > (*a)[i][k]+(*a)[k][j] && (*a)[i][j]!=-1 && (*a)[i][k]!=-1 && (*a)[k][j]!=-1)
				{
					(*a)[i][j] = (*a)[i][k]+(*a)[k][j];
				}
			}
}

void read (int ***a, int *n, location **p, char *fisier1in, char *fisier2in)
{
	FILE *coord, *avarii;
	char useless_buffer[20], buf1[20], buf2[20];
	int x1, y1, r2, x2, y2, r1, x3, y3, r3;

	coord = fopen(fisier1in,"r");
	fscanf(coord, "%d", n);

	int j=1, i;
	int n1, n2;

	*p = (location*)calloc((*n)+1, sizeof(location));
	*a = (int**)calloc((*n)+1, sizeof(int));
	for (i=0; i<=(*n)+1; i++)
	{
		(*a)[i] = (int*)calloc((*n)+1, sizeof(int));
	}

	for (i=1; i<= *n; i++)
	{
		fscanf(coord, "%s", (*p)[i].name);
		fscanf(coord, "%s %d %d %d", useless_buffer, &x1, &y1, &r1);
		fscanf(coord, "%s %d %d %d", useless_buffer, &x2, &y2, &r2);
		fscanf(coord, "%s %d %d %d", useless_buffer, &x3, &y3, &r3);
		(*p)[i].x = coord_x( x1,  y1,  r1,  x2,  y2,  r2,  x3,  y3,  r3);
		(*p)[i].y = coord_y( x1,  y1,  r1,  x2,  y2,  r2,  x3,  y3,  r3);
	}
	for (i=1; i<= *n; i++)
	{
		for (j=1; j<= *n; j++)
		{
			(*a)[i][j] = distance((*p)[i], (*p)[j]);
		}
	}
	avarii = fopen(fisier2in, "r");
	while(fscanf(avarii, "%s %s", buf1, buf2)!=EOF)
	{
		for (i=1; i<= *n; i++)
		{
			if (!strcmp(buf1, (*p)[i].name))
			{
				n1 = i;
			}
			if (!strcmp(buf2, (*p)[i].name))
			{
				n2 = i;
			}
		}
		(*a)[n1][n2] = -1;
	}

}
void write(location *p, int x, int n, char *fiser1out, char *fisier2out)
{
    FILE *coord, *rez;
    coord = fopen(fiser1out, "w");
    rez = fopen(fisier2out, "w");
    int i;
    for (i=1; i<=n; i++)
    {
        fprintf(coord, "%d %d\n", p[i].x, p[i].y);
    }
    fprintf(rez, "%d", x);

    fclose(coord);
    fclose(rez);
}

int main(int argc, char *argv[])
{
    char fisier1in[20], fisier2in[20], dest[20], fisier1out[20], fisier2out[20];
    strcpy(fisier1in, argv[0]);
    strcpy(fisier2in, argv[1]);
    strcpy(dest, argv[2]);
    strcpy(fisier1out, argv[3]);
    strcpy(fisier2out, argv[4]);

    int **a, n, x, i;
    location *p;
    read(&a, &n, &p, fisier1in, fisier2in);
    rf(&a, n);

    for (i=1; i<= n; i++)
		{
			if (!strcmp(dest, p[i].name))
			{
				x = a[1][i];
			}
		}

    write(p, x, n, fisier1out, fisier2out);

    return 0;
}