카테고리

CamelACT (9)
UVa (3)
Basics (4)
Information (2)
Statistics Graph

'Gopher'에 해당되는 글 1건

  1. 2012.12.01 [UVa]10310 - Dog and Gopher

관련 링크 : http://acm.uva.es/p/v103/10310.html


Input: standard input

Output: standard output

Time Limit: 1 second

Memory Limit: 32 MB

 

A large field has a gopher and a dog. The dog wants to eat the gopher, while the gopher wants to run to safety through one of several gopher holes dug in the surface of the field.

Neither the dog nor the gopher is a math major; however, neither is entirely stupid. The gopher decides on a particular gopher hole and heads for that hole in a straight line at a fixed speed. The dog, which is very good at reading body language, anticipates which hole the gopher has chosen, and heads at double the speed of the gopher to the hole, where it intends to gobble up the gopher. If the dog reaches the hole first, the gopher gets gobbled; otherwise, the gopher escapes.

You have to select a hole for the gopher through which it can escape, if such a hole exists.


Input

The input file contains several sets of input. The first line of each set contains one integer and four floating point numbers. The integer n denotes how many holes are in the set and the four floating point numbers denote the (x,y) coordinates of the gopher followed by the (x,y) coordinates of the dog. Subsequent n lines of input each contain two floating point numbers: the (x, y) coordinates of a gopher hole. All distances are in meters; to the nearest mm. Input is terminated by end of file. There is a blank line between two consecutive sets.


Output

Your should output a single line for each set of input. For each set, if the gopher can escape the output line should read "The gopher can escape through the hole at (x,y)." identifying the appropriate hole to the nearest mm. Otherwise the output line should read "The gopher cannot escape." If the gopher may escape through more than one hole, report the one that appears first in the input. There are not more than 1000 gopher holes in a set of input and all coordinates are between -10000 and +10000.


Sample Input:

1 1.000 1.000 2.000 2.000
1.500 1.500
 
2 2.000 2.000 1.000 1.000
1.500 1.500
2.500 2.500

Sample Output

The gopher cannot escape.
The gopher can escape through the hole at (2.500,2.500).


 첫 블로그 게시물을 올린다. 이 문제는 며칠 전에 속해 있던 단체에서 풀어 보았던 문제이다. 난이도는 별 한 개 정도이다.

 UVa 사이트를 이용하면서 가장 고된 것은 알고리즘을 풀었을 때 답이 맞냐, 안 맞냐가 아니라 우선 영어로 된 문제를 이해하는 것이다.

 블로그의 첫 게시물인 만큼 따뜻한 마음으로 대강의 해석도 해 보겠다.

 

Problem

 커다란 공터에 개와 다람쥐가 있다. 개는 다람쥐를 쳐 먹길 원한다. 반면에 다람쥐는 안전한 곳으로 도망가길 원한다. 그것은 바로 공터의 표면에 있는 몇 개의 구멍을 통해서다결코 개와 다람쥐는 수학 천재가 아니다? 하지만 둘 다 바보도 아니다. 다람쥐는 구멍 한 개를 정한 다음 그 구멍을 향해 일정한 속도로 직선으로 뛰어간다개는 유연해서 다람쥐가 어느 구멍으로 들어가기로 했는지 안다개는 다람쥐보다 두 배의 속도로 구멍을 향해 뛰어간다다람쥐는 개가 구멍에 먼저 도착하면 잡혀 먹히고, 그렇지 않으면 도망칠 수 있다다람쥐로부터 어떤 구멍으로 숨어야 할지 결정하는데 도움을 줄만한 프로그램을 만들어 보아라.

 

Input

 첫 번째 라인에는 한 개의 정수와 네 개의 실수 포인터를 넣는다. 정수 n은 얼마나 많은 구멍을 넣을 것인지 구멍 수를 입력한다. 네 개의 실수는 각각 다람쥐의 x, y 좌표, 개의 x, y 좌표이다. 그 다음 n 만큼 구멍의 x, y 좌표를 입력한다. 모든 거리는 미터이다. 입력은 파일의 끝일 때 종료되며 그 다음은 해석이 안 된다.

 

Output

 너는 토해 내야 한다. 한 줄을. 각각의 세트에 맞게 다람쥐가 탈출 하였다면 "The gopher can escape through the hole at (x,y)."를 출력하고 x, y는 해당 구멍의 좌표를 넣는다. 만약에 다람쥐가 탈출을 못 했다면 "The gopher cannot escape."를 출력한다.

 구멍의 개수는 1000개를 넘기지 말고, 좌표계는 -10000에서 +10000 사이로 하여라.

 

 우선 내가 알고리즘을 풀었다는 감동이 며칠 전에 비해 상당히 줄어들어 더 이상 쓸 의욕이 안 난다. 첫 게시물인데 약간 고되다. 아래 답은 몇 가지 주석을 달아 놓았으니 그 부분은 알아서 채워 넣었으면 좋겠다.


#include <cmath>
#include <iostream>

using namespace std;

int main (void) {
	int hole_count;
	double gopherX;
	double gopherY;
	double dogX;
	double dogY;

	cin >> hole_count >> gopherX >> gopherY >> dogX >> dogY;

	double holeX[1000];
	double holeY[1000];

	for(int j = 0 ; j < hole_count ; j ++){
		cin >> holeX[j] >> holeY[j];
	}

	bool catch_gopher = false;
	int catch_index = 0;

	for(int j = 0 ; j < hole_count ; j ++){
		double gopher_range = sqrt(pow(holeX[j] - gopherX, 2) + pow(holeY[j] - gopherY,2));
		double dog_range    = sqrt(pow(holeX[j] - dogX, 2) + pow(holeY[j] - dogY,2));

		catch_index = j;

		if(gopher_range * 2 < dog_range){ // 탈출 실패
			catch_gopher =  true;
			break;
		}
	}


	if(!catch_gopher){
		/*
		*/
	} else {
		/*
		*/
	}
}



신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'UVa' 카테고리의 다른 글

[UVa]102 - Ecological Bin Packing  (1) 2012.12.05
[UVa]151 - Power Crisis  (0) 2012.12.04
[UVa]10310 - Dog and Gopher  (0) 2012.12.01
UVa l 2012.12.01 21:30
1 
get rsstistory! Tistory Tistory 가입하기!

티스토리 툴바