There is a large Room in the pyramid called room-of-no-return, and unfortunately Magicpig is currently trapped in this Room. There are some hooks on the floor of the room. On the walls of the room there is some ancient Egyptian writing: “If you want to escape from here, you must connect all these hooks with ropes, then a secret door opens and you will be free. If you can’t, you’ll be stuck here forever.” Fortunately, Magicpig has a rope of length L that he can cut into segments with two hooks attached to each segment. If he can connect all the hooks with this rope and the connected rope does not loop, he can escape! Kinfkong wants to know if he can escape.

Input format:

The input contains one or more data sets. In line 1 of each input data set there are two integers n and L, where n is the number of hooks and L is the length of the rope. The next n lines contain a series of coordinates for the hook, each of which is a pair of non-negative integers less than 32768, separated by Spaces (2<=n<=100, L<=32767). A zero number of hooks indicates the end of input.

Output format:

For each dataset, if Magicpig can escape, print a string of “Success!” , otherwise print “Poor Magicpig! .

Example Input:

2 1
0 0
1 1 
2 2
0 0
1 1
0
Copy the code

Example output:

Poor magicpig!
Success!
Copy the code

#include<bits/stdc++.h>
using namespace std;
#define maxn 102
int n, m;
int cnt;/ / the number of edges
int root[maxn];
struct node {
	int x, y;/ / coordinates
	int idx;/ / the subscript
}points[maxn];
struct node2 {
	int u, v;/ / the endpoint
	double cost;/ / has a weight
}edge[maxn*maxn];
bool cmp(node2 a, node2 b) {
	return a.cost < b.cost;
}
int Find(int x) {
	return root[x] == x ? x : root[x] = Find(root[x]);
}
double Kruskal(a) {
	for (int i = 0; i <= n; i++)
		root[i] = i;
	sort(edge + 1, edge + cnt, cmp);
	double ans = 0;
	for (int i = 1; i <= cnt; i++) {
		int u = Find(edge[i].u);
		int v = Find(edge[i].v);
		if(u ! = v) { root[u] = v;//Unionans += edge[i].cost; }}// Determine the disconnected graph
	return ans;
}
int main(a) {
	while (~scanf("%d", &n) && n ! =0) {
		scanf("%d", &m);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &points[i].x, &points[i].y);
			points[i].idx = i;
		}
		cnt = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				edge[cnt].u = points[i].idx;
				edge[cnt].v = points[j].idx;
				double cost = pow(points[i].x - points[j].x, 2);
				cost += pow(points[i].y - points[j].y, 2);
				cost = sqrt(cost); edge[cnt].cost = cost; cnt++; }}double ans = Kruskal(a);if (ans > m)printf("Poor magicpig! \n");
		else printf("Success! \n");
	}
	return 0;
}
Copy the code