Source code for submission s1217

Go to diff to previous submission

Cockchaf.java

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Comparator;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.PriorityQueue;
  9. import java.util.Queue;
  10. import java.util.Scanner;
  11. import java.util.StringTokenizer;
  12.  
  13. public class Cockchaf {
  14.     static class Step implements Comparable<Step>{
  15.         Point p;
  16.         double dx,dy,dz;
  17.         double time;
  18.  
  19.         Step (Point p_, double dx_, double dy_, double dz_,double time_){
  20.             p = p_;
  21.             dx = dx_;
  22.             dy = dy_;
  23.             dz = dz_;
  24.             time = time_;
  25.         }
  26.  
  27.         public int compareTo(Step s) {
  28.             double e = 0.0000001;
  29.             if (s.time-time > e) return -1;
  30.             if (time-s.time > e) return 1;
  31.             return 0;
  32.         }
  33.     }
  34.  
  35.     static class Point {
  36.  
  37.         @Override
  38.         public boolean equals(Object obj) {
  39.             if (obj == null) {
  40.                 return false;
  41.             }
  42.             if (getClass() != obj.getClass()) {
  43.                 return false;
  44.             }
  45.             final Point other = (Point) obj;
  46.             if (this.x != other.x) {
  47.                 return false;
  48.             }
  49.             if (this.y != other.y) {
  50.                 return false;
  51.             }
  52.             if (this.z != other.z) {
  53.                 return false;
  54.             }
  55.             return true;
  56.         }
  57.  
  58.         @Override
  59.         public int hashCode() {
  60.             int hash = 3;
  61.             hash = 47 * hash + this.x;
  62.             hash = 47 * hash + this.y;
  63.             hash = 47 * hash + this.z;
  64.             return hash;
  65.         }
  66.  
  67.         int x,y,z;
  68.         List<Point> e = new ArrayList<Point>();
  69.  
  70.         Point(int x,int y, int z){
  71.             this.x = x;
  72.             this.y = y;
  73.             this.z = z;
  74.  
  75.         }
  76.  
  77.     };
  78.  
  79.     static double length(double x1, double x2, double x3, double y1, double y2, double y3){
  80.         return Math.sqrt((x1-y1)*(x1-y1)+(x2-y2)*(x2-y2)+(x3-y3)*(x3-y3));
  81.     }
  82.  
  83.     static double degToTurn(double u1,double u2,double u3,double v1,double v2,double v3){
  84.         double d;
  85.         d = Math.acos((u1*v1+u2*v2+u3*v3)/(length(0,0,0,u1,u2,u3)*length(0,0,0,v1,v2,v3)));
  86.         return d*180/Math.PI;
  87.     }
  88.  
  89.     public static void main(String[] args) throws IOException {
  90.         //Scanner sc = new Scanner(System.in);
  92.         do {
  93.             String line = br.readLine();
  94.             if(line == null) {
  95.                 break;
  96.             }
  98.             int N = Integer.parseInt(st.nextToken());
  99.             int S = Integer.parseInt(st.nextToken());
  100.             int T = Integer.parseInt(st.nextToken());
  101.  
  102.             st = new StringTokenizer(br.readLine());
  103.             Point end = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  104.             Point start = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  105.             List<Point> points = new ArrayList<Point>();
  106.             points.add(start);
  107.             points.add(end);
  108.  
  109.             for (int i=0; i<N; i++){
  110.                 st = new StringTokenizer(br.readLine());
  111.                 Point p1 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  112.                 Point p2 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
  113.                 if (p1.equals(p2)) continue;
  114.                 Point p1R = null, p2R = null;
  115.                 for (int j=0; j<points.size(); j++){
  116.                     if (points.get(j).equals(p1)){
  117.                         p1R = points.get(j);
  118.                     }
  119.                     if (points.get(j).equals(p2)){
  120.                         p2R = points.get(j);
  121.                     }
  122.                     if (p1R != null && p2R != null) break;
  123.                 }
  124.                 if (p1R == null){
  125.                     p1R = p1;
  126.                     points.add(p1R);
  127.                 }
  128.                 if (p2R == null){
  129.                     p2R = p2;
  130.                     points.add(p2R);
  131.                 }
  132.  
  133.                 p1R.e.add(p2R);
  134.                 p2R.e.add(p1R);
  135.             }
  136.  
  137.             /*Comparator<Step>  comp = new Comparator<Step>(){
  138.  
  139.                 public int compare(Step arg0, Step arg1) {
  140.                     if (arg0.p == end && arg1.p != end){
  141.                         return 1;
  142.                     }else if (arg0.p != end && arg1.p == end){
  143.                         return -1;
  144.                     }
  145.                     return arg0.compareTo(arg1);
  146.                 }
  147.                 
  148.             };*/
  149.  
  150.             if (start.equals(end)){
  151.                 System.out.println("0.0000");
  152.                 continue;
  153.             }
  154.             Queue<Step> q = new PriorityQueue<Step>();
  155.  
  156.             //init
  157.             for (int i=0; i<start.e.size(); i++){
  158.                 double d = length(start.x, start.y, start.z, start.e.get(i).x, start.e.get(i).y, start.e.get(i).z);
  159.                 double dx = start.e.get(i).x - start.x;
  160.                 double dy = start.e.get(i).y - start.y;
  161.                 double dz = start.e.get(i).z - start.z;
  162.                 q.add(new Step(start.e.get(i), dx, dy, dz, d/S));
  163.                 System.err.println(d/S);
  164.             }
  165.  
  166.             while (true) {
  167.                 Step c = q.poll();
  168.                 if (c.p.equals(end)){
  169.                     System.out.printf("%.4f\n", c.time);
  170.                     break;
  171.                 }
  172.                 for (int i=0; i<c.p.e.size(); i++){
  173.                     double d = length(c.p.x,c.p.y,c.p.z,c.p.e.get(i).x,c.p.e.get(i).y, c.p.e.get(i).z);
  174.                     double dx = c.p.e.get(i).x  - c.p.x;
  175.                     double dy = c.p.e.get(i).y  - c.p.y;
  176.                     double dz = c.p.e.get(i).z  - c.p.z;
  177.                     double t = degToTurn(c.dx, c.dy, c.dz, dx, dy, dz);
  178.                     q.add(new Step(c.p.e.get(i), dx, dy, dz, c.time + d/S + t/T));
  179.                 }
  180.             }
  181.  
  182.         } while(true);
  183.     }
  184.  
  185.  
  186. }
  187.  

Diff to submission s1156

Cockchaf.java

--- c4.s1156.cteam018.cockchaf.java.0.Cockchaf.java
+++ c4.s1217.cteam018.cockchaf.java.0.Cockchaf.java
@@ -1,8 +1,13 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
 import java.util.ArrayList;
 import java.util.Comparator;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.PriorityQueue;
 import java.util.Queue;
 import java.util.Scanner;
+import java.util.StringTokenizer;
 
 public class Cockchaf {
@@ -82,12 +87,20 @@
     }
     
-    public static void main(String[] args) {
-        Scanner sc = new Scanner(System.in);
-        while (sc.hasNextInt()){
-            int N = sc.nextInt();
-            int S = sc.nextInt();
-            int T = sc.nextInt();
-            Point start = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
-            final Point end = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
+    public static void main(String[] args) throws IOException {
+        //Scanner sc = new Scanner(System.in);
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+        do {
+            String line = br.readLine();
+            if(line == null) {
+                break;
+            }
+            StringTokenizer st = new StringTokenizer(line);
+            int N = Integer.parseInt(st.nextToken());
+            int S = Integer.parseInt(st.nextToken());
+            int T = Integer.parseInt(st.nextToken());
+            
+            st = new StringTokenizer(br.readLine());
+            Point end = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
+            Point start = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
             List<Point> points = new ArrayList<Point>();
             points.add(start);
@@ -95,6 +108,7 @@
            
             for (int i=0; i<N; i++){
-                Point p1 = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
-                Point p2 = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
+                st = new StringTokenizer(br.readLine());
+                Point p1 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
+                Point p2 = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
                 if (p1.equals(p2)) continue;
                 Point p1R = null, p2R = null;
@@ -166,5 +180,5 @@
             }
             
-        }
+        } while(true);
     }