2013
11-11

# Dog & Gopher

A large field has a dog and a gopher. 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 been retained by the gopher to select a hole through which it can escape, if such a hole exists.

The first line of input contains four floating point numbers: the (x,y) coordinates of the gopher followed by the (x,y) coordinates of the dog. Subsequent lines of input each contain two floating point numbers: the (x,y) coordinates of a gopher hole. All distances are in metres, to the nearest mm.

Your output should consist of a single line. If the gopher can escape the 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, choose the first one in the input. If the gopher and dog reach the hole at the same time, the gopher gets gobbled. There are not more than 1000 gopher holes and all coordinates are between -10000 and +10000.

1.000 1.000 2.000 2.000
1.500 1.500


The gopher cannot escape.


Sample Input 2

2.000 2.000 1.000 1.000

1.500 1.500

2.500 2.500

Output for Sample Input 2

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

//* @author 洪晓鹏<[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */>
import java.util.Scanner;

public class Main{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
double x1 = in.nextDouble();
double y1 = in.nextDouble();
double x2 = in.nextDouble();
double y2 = in.nextDouble();
//double r1 = 0;
//double r2 = 0;
//double d3 = 0;
boolean canEscape = false;
while(in.hasNext())
{
String s1 = in.next();
in.skip(" ");
String s2 = in.nextLine();
//in.nextLine();
double x3 = Double.parseDouble(s1);
double y3 = Double.parseDouble(s2);
double d1 = (x3 - x1)*(x3 - x1) + (y3 - y1)*(y3 - y1);
double d2 = (x3 - x2)*(x3 - x2) + (y3 - y2)*(y3 - y2);
if(d2 > 4 *  d1)
{
canEscape = true;
System.out.print("The gopher can escape through the hole at ("+s1+','+s2+").");
break;
}
}

if(canEscape == false)
System.out.println("The gopher cannot escape.");
}
}

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。