Source code for submission s1156

Go to diff to previous submission

Cockchaf.java

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

Diff to submission s1086

Cockchaf.java

--- c4.s1086.cteam018.cockchaf.java.0.Cockchaf.java
+++ c4.s1156.cteam018.cockchaf.java.0.Cockchaf.java
@@ -1,19 +1,9 @@
-
 import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.HashSet;
+import java.util.Comparator;
 import java.util.List;
-import java.util.Map;
 import java.util.PriorityQueue;
 import java.util.Queue;
 import java.util.Scanner;
-import java.util.Set;
-
 
-
-/**
- *
- * @author cteam018
- */
 public class Cockchaf {
     static class Step implements Comparable<Step>{
@@ -99,11 +89,13 @@
             int T = sc.nextInt();
             Point start = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
-            Point end = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
+            final Point end = new Point(sc.nextInt(),sc.nextInt(),sc.nextInt());
             List<Point> points = new ArrayList<Point>();
             points.add(start);
             points.add(end);
+           
             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());
+                if (p1.equals(p2)) continue;
                 Point p1R = null, p2R = null;
                 for (int j=0; j<points.size(); j++){
@@ -129,5 +121,23 @@
             }
             
+            /*Comparator<Step>  comp = new Comparator<Step>(){
+
+                public int compare(Step arg0, Step arg1) {
+                    if (arg0.p == end && arg1.p != end){
+                        return 1;
+                    }else if (arg0.p != end && arg1.p == end){
+                        return -1;
+                    }
+                    return arg0.compareTo(arg1);
+                }
+                
+            };*/
+            
+            if (start.equals(end)){
+                System.out.println("0.0000");
+                continue;
+            }
             Queue<Step> q = new PriorityQueue<Step>();
+            
             //init
             for (int i=0; i<start.e.size(); i++){