[UVA10310]Dog and Gopher

A large eld 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 eld. 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 xed 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 rst, 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 le contains several sets of input. The rst line of each set contains one integer and four oating point numbers. The integer n denotes how many holes are in the set and the four oating 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 oating 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 le. 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 rst 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).

題意: 計算距離回答Gopher是否被Dog吃到，且D的速度是G的兩倍。想法:距離問題，注意精確度以及距離剛好是兩倍的情形也算…。

#include <stdio.h> 
#include <stdlib.h>   
int main() { 
  int n; 
  double x1,x2,y1,y2; 
  double hx,hy; 
  bool end = false; 
  while(~scanf("%d %lf %lf %lf %lf",&n,&x1,&y1,&x2,&y2)) { 
    end = false; 
    //printf("%d %f %f %f %f\n",n,x1,y1,x2,y2); 
    for(int i = 0 ; i < n ; ++i) { 
      scanf("%lf %lf",&hx,&hy); 
      if(!end) { 
        if( 4.0 * ((hx-x1)*(hx-x1)+(hy-y1)*(hy-y1)) <= ((hx-x2)*(hx-x2)+(hy-y2)*(hy-y2)) ) { 
          printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",hx,hy); 
          end = true; 
        }
      } 
    } 
    if(!end)printf("The gopher cannot escape.\n"); 
  } 
  return 0; 
}