Saving James Bond - Hard Version

编程语言：Java
题目：

题解：路径还原罢了，每次跳到下一个点的时候记录一下就可以了，还以为能一次过，结果竟然可以一次跳到岸上（咱们强大的詹姆斯·邦德~~），也不想去优化程序了，直接一个外部条件判断解决；一个参数的distance是第一次跳的距离，后面的是判断两点之间的距离；此外，题目还有一个要求，在有很多最短路径的时候选择第一条最短的，解决方法就是按到岸的距离的远近来排序，这样还可以提前结束循环（到岸的距离太长了，一次跳不上去，那后面的也跳不上去了呀）；最后这道题用Scanner也不会超时的。
结果：AC

import java.io.*;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Scanner sc = new Scanner(new BufferedInputStream(System.in));

    static crocodile[] c=new crocodile[102];
    static boolean[] f=new boolean[102];
    static int[] prev=new int[102];
    static double radius=7.5;
    static int n,d;

    public static void main(String[] args) throws IOException {
        in.nextToken();
        n= (int) in.nval;
        in.nextToken();
        d= (int) in.nval;
        for(int i=1;i<=n;i++){
            in.nextToken();
            int x= (int) in.nval;
            in.nextToken();
            int y= (int) in.nval;
            c[i]=new crocodile(x,y);
        }
        if(d>=50-radius)
            out.println(1);
        else{
            Arrays.sort(c,1,n+1, new Comparator<crocodile>() {
                @Override
                public int compare(crocodile o1, crocodile o2) {
                    return o1.x*o1.x+o1.y*o1.y-o2.x*o2.x-o2.y*o2.y;
                }
            });
            int ways=Integer.MAX_VALUE;
            Deque<Integer> stack=new LinkedList<>();
            for(int i=1;i<=n;i++){
                if(distance(i)){
                    Arrays.fill(prev,-1);
                    Arrays.fill(f,false);
                    point p=bfs(i);
                    if(p!=null&&p.step<ways){
                        stack.clear();
                        stack.push(p.i);
                        while(prev[p.i]!=-1){
                            stack.push(prev[p.i]);
                            p.i=prev[p.i];
                        }
                        ways=p.step;
                    }
                }else{
                    break;
                }
            }
            if(ways==Integer.MAX_VALUE){
                out.println(0);
            }else{
                out.println(stack.size()+1);
                while(stack.size()>0){
                    int i=stack.pop();
                    out.println(c[i].x+" "+c[i].y);
                }
            }
        }
        out.flush();
    }

    private static point bfs(int i) {
        LinkedBlockingQueue<point> que=new LinkedBlockingQueue<>();
        que.add(new point(i,1));
        f[i]=true;
        while(!que.isEmpty()){
            point p=que.poll();
            if(Math.abs(c[p.i].x)>=50-d||Math.abs(c[p.i].y)>=50-d)
                return p;
            for(int j=1;j<=n;j++){
                if(!f[j]&&distance(p.i,j)){
                    que.add(new point(j,p.step+1));
                    prev[j]=p.i;
                    f[j]=true;
                }
            }
        }
        return null;
    }

    private static boolean distance(int i) {
        if(Math.sqrt(c[i].x*c[i].x+c[i].y*c[i].y)<=d+radius)
            return true;
        else
            return false;
    }

    private static boolean distance(int i, int j) {
        int x=c[i].x-c[j].x;
        int y=c[i].y-c[j].y;
        if(Math.sqrt(x*x+y*y)<=d)
            return true;
        else
            return false;
    }

}
class point{
    int i;
    int step;

    public point(int i, int step) {
        this.i = i;
        this.step = step;
    }
}
class crocodile{
    int x;
    int y;

    public crocodile(int x, int y) {
        this.x = x;
        this.y = y;
    }
}