The Java Program: H_robot/robotYiu.java

  1 /*
  2 ACM ICPC Southeast Regional Contest 2009
  3 
  4 Robot Challenge
  5 
  6 Author: Yiu Yu Ho
  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                         //(x[i], y[i], p[i]) are target location and penality
 39                         //psum[i] = p[0] + p[1] + ... + p[i]
 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                         //cost[i]: the optimal cost of starting at (0, 0) visiting/skipping target points {1, 2, ..., i-1} and 
 51                         //visiting (and stopping for a second at) target point (x[i], y[i])
 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                                 //last point may be point i-1
 59                                 cost[i] = cost[i-1] + dist(i-1, i) + 1.0;
 60 
 61                                 //try other possibilities, j, as the last point
 62                                 for(j=i-2;j>=0;--j)
 63                                 {
 64                                         //If the previous point is j, then the penality is p[j+1] + p[j+2] + ... + p[i-1]
 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         //distance between point (x[i], y[i]) and (x[j], y[j])
 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 }