M-Judge 10146 Carrot Tour

ACM-ICPC JAG Summer Camp 2010, Day 3
Problem B: Carrot Tour
より

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>28;
    final double EPS=1e-9;

    int n;
    double r;
    double theta;
    int[] xs, ys;
    double[][] cost;
    boolean[][][] can;

    void run(){
        n=sc.nextInt();
        r=sc.nextDouble();
        theta=sc.nextDouble();
        xs=new int[n];
        ys=new int[n];
        cost=new double[n][n];
        can=new boolean[n][n][n];
        for(int i=0; i<n; i++){
            xs[i]=sc.nextInt();
            ys[i]=sc.nextInt();
        }
        
        for(int j=0; j<n; j++){
            for(int i=0; i<n; i++){
                double dx=xs[j]-xs[i];
                double dy=ys[j]-ys[i];
                if(i==j)
                    cost[j][i]=INF;
                else
                    cost[j][i]=Math.sqrt(dx*dx+dy*dy);
            }
        }

        // i->j->k
        for(int k=0; k<n; k++){
            for(int j=0; j<n; j++){
                if(j==k)
                    continue;
                for(int i=0; i<n; i++){
                    if(i==k||i==j)
                        continue;
                    double x1=xs[j]-xs[i];
                    double y1=ys[j]-ys[i];
                    double x2=xs[k]-xs[j];
                    double y2=ys[k]-ys[j];
                    double cost=(x1*x2+y1*y2)
                            /Math.sqrt((x1*x1+y1*y1)*(x2*x2+y2*y2));
                    if(Math.cos(Math.toRadians(theta))<cost+EPS)
                        can[i][j][k]=true;
                }
            }
        }

        double dp[][]=new double[n][n];
        double t[][]=new double[n][n];

        for(int j=0; j<n; j++)
            for(int i=0; i<n; i++)
                t[i][j]=INF;
        for(int j=0; j<n; j++)
            t[0][j]=cost[0][j];

        for(int c=0;; c++){
            boolean f=false;
            for(int j=0; j<n; j++)
                for(int i=0; i<n; i++)
                    if(t[j][i]<r+EPS)
                        f=true;
            if(!f){
                println(c+"");
                return;
            }

            for(int k=0; k<n; k++){
                for(int j=0; j<n; j++){
                    dp[j][k]=INF;
                    for(int i=0; i<n; i++){
                        if(can[i][j][k]){
                            dp[j][k]=Math.min(dp[j][k], t[i][j]+cost[j][k]);
                        }
                    }
                }
            }
            for(int j=0; j<n; j++)
                for(int i=0; i<n; i++)
                    t[j][i]=dp[j][i];
        }
    }

    public static void main(String[] args){
        new Main().run();
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }

}