The Java Program: H_robot/robotYiu.java
1
2
3
4
5
6
7
8
9 import java.io.*;
10 import java.util.*;
11 import java.text.*;
12
13 public class robotYiu
14 {
15 public Scanner in = new Scanner(System.in);
16 public PrintStream out = System.out;
17 public DecimalFormat fmt = new DecimalFormat("0.000");
18
19 public final double T50 = 1e50;
20 public final double tol = 1e-12;
21
22 public int n;
23 public int[] x, y, p, psum;
24
25 public void main()
26 {
27 int i, j, k;
28
29 n = in.nextInt();
30 while(n > 0)
31 {
32 x = new int[n+2];
33 y = new int[n+2];
34 p = new int[n+2];
35 psum = new int[n+2];
36
37 x[0] = y[0] = 0;
38
39
40 for(i=1;i<=n;++i)
41 {
42 x[i] = in.nextInt();
43 y[i] = in.nextInt();
44 p[i] = in.nextInt();
45 psum[i] = psum[i-1] + p[i];
46 }
47 x[n+1] = y[n+1] = 100;
48 psum[n+1] = psum[n];
49
50
51
52 double[] cost = new double[n+2];
53 Arrays.fill(cost, T50);
54 cost[0] = 0.0;
55
56 for(i=1;i<=n+1;++i)
57 {
58
59 cost[i] = cost[i-1] + dist(i-1, i) + 1.0;
60
61
62 for(j=i-2;j>=0;--j)
63 {
64
65 cost[i] = Math.min(cost[i], cost[j] + dist(j, i) + 1.0 + psum[i-1] - psum[j]);
66 if(cost[i] < psum[i-1] - psum[j]) break;
67 }
68 }
69
70 out.println(fmt.format(cost[n+1] + tol));
71
72 n = in.nextInt();
73 }
74 }
75
76
77 public double dist(int i, int j)
78 {
79 double dx, dy;
80 dx = x[i] - x[j];
81 dy = y[i] - y[j];
82 return Math.sqrt(dx*dx + dy*dy);
83 }
84
85 public static void main(String[] args)
86 {
87 long startTime = System.currentTimeMillis();
88 (new robotYiu()).main();
89 long endTime = System.currentTimeMillis();
90
91 System.err.println("Time = " + (endTime - startTime) + "(ms)");
92 }
93 }