M-Judge 10146 Carrot Tour

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>28;  
11.     final double EPS=1e-9;  
12.   
13.     int n;  
14.     double r;  
15.     double theta;  
16.     int[] xs, ys;  
17.     double[][] cost;  
18.     boolean[][][] can;  
19.   
20.     void run(){  
21.         n=sc.nextInt();  
22.         r=sc.nextDouble();  
23.         theta=sc.nextDouble();  
24.         xs=new int[n];  
25.         ys=new int[n];  
26.         cost=new double[n][n];  
27.         can=new boolean[n][n][n];  
28.         for(int i=0; i<n; i++){  
29.             xs[i]=sc.nextInt();  
30.             ys[i]=sc.nextInt();  
31.         }  
32.           
33.         for(int j=0; j<n; j++){  
34.             for(int i=0; i<n; i++){  
35.                 double dx=xs[j]-xs[i];  
36.                 double dy=ys[j]-ys[i];  
37.                 if(i==j)  
38.                     cost[j][i]=INF;  
39.                 else  
40.                     cost[j][i]=Math.sqrt(dx*dx+dy*dy);  
41.             }  
42.         }  
43.   
44.         // i->j->k  
45.         for(int k=0; k<n; k++){  
46.             for(int j=0; j<n; j++){  
47.                 if(j==k)  
48.                     continue;  
49.                 for(int i=0; i<n; i++){  
50.                     if(i==k||i==j)  
51.                         continue;  
52.                     double x1=xs[j]-xs[i];  
53.                     double y1=ys[j]-ys[i];  
54.                     double x2=xs[k]-xs[j];  
55.                     double y2=ys[k]-ys[j];  
56.                     double cost=(x1*x2+y1*y2)  
57.                             /Math.sqrt((x1*x1+y1*y1)*(x2*x2+y2*y2));  
58.                     if(Math.cos(Math.toRadians(theta))<cost+EPS)  
59.                         can[i][j][k]=true;  
60.                 }  
61.             }  
62.         }  
63.   
64.         double dp[][]=new double[n][n];  
65.         double t[][]=new double[n][n];  
66.   
67.         for(int j=0; j<n; j++)  
68.             for(int i=0; i<n; i++)  
69.                 t[i][j]=INF;  
70.         for(int j=0; j<n; j++)  
71.             t[0][j]=cost[0][j];  
72.   
73.         for(int c=0;; c++){  
74.             boolean f=false;  
75.             for(int j=0; j<n; j++)  
76.                 for(int i=0; i<n; i++)  
77.                     if(t[j][i]<r+EPS)  
78.                         f=true;  
79.             if(!f){  
80.                 println(c+"");  
81.                 return;  
82.             }  
83.   
84.             for(int k=0; k<n; k++){  
85.                 for(int j=0; j<n; j++){  
86.                     dp[j][k]=INF;  
87.                     for(int i=0; i<n; i++){  
88.                         if(can[i][j][k]){  
89.                             dp[j][k]=Math.min(dp[j][k], t[i][j]+cost[j][k]);  
90.                         }  
91.                     }  
92.                 }  
93.             }  
94.             for(int j=0; j<n; j++)  
95.                 for(int i=0; i<n; i++)  
96.                     t[j][i]=dp[j][i];  
97.         }  
98.     }  
99.   
100.     public static void main(String[] args){  
101.         new Main().run();  
102.     }  
103.   
104.     void print(String s){  
105.         System.out.print(s);  
106.     }  
107.   
108.     void println(String s){  
109.         System.out.println(s);  
110.     }  
111.   
112.     void println(){  
113.         System.out.println();  
114.     }  
115.   
116. }  

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();
    }

}