Source code for submission s1227

Cockchaf.java

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.PriorityQueue;
  7. import java.util.Scanner;
  8.  
  9. public class Cockchaf {
  10. private static class Vrch implements Comparable<Vrch>{
  11. public double d;
  12. public Vrchol v;
  13. public Vrchol p;
  14.  
  15. public Vrch(double d, Vrchol v, Vrchol p) {
  16. this.d = d;
  17. this.v = v;
  18. this.p = p;
  19. }
  20.  
  21. @Override
  22. public int compareTo(Vrch o) {
  23. return (int)Math.signum(o.d-d);
  24. }
  25.  
  26. }
  27.  
  28. public static double a2(double a){
  29. return a*a;
  30. }
  31.  
  32. private static class Vrchol{
  33. public int x,y,z,p;
  34. public List<Vrchol> sused;
  35.  
  36. public Vrchol(int x, int y, int z) {
  37. this.x = x;
  38. this.y = y;
  39. this.z = z;
  40. sused = new LinkedList<Vrchol>();
  41. }
  42.  
  43. public double vzdialenost(Vrchol v){
  44. return Math.sqrt(a2(v.x-x)+a2(v.y-y)+a2(v.z-z));
  45. }
  46.  
  47.  
  48. public boolean equals(Vrchol v) {
  49. if(v.x==x && v.y==y && v.z==z){
  50. return true;
  51. } else {
  52. return false;
  53. }
  54. }
  55.  
  56. @Override
  57. public String toString() {
  58. return "[" + x + ","+y+","+z+"] ";
  59. }
  60. }
  61.  
  62. private static double uhol(Vrchol v1, Vrchol v2, Vrchol v3){
  63. int dx1 = v2.x-v1.x;
  64. int dy1 = v2.y-v1.y;
  65. int dz1 = v2.z-v1.z;
  66.  
  67. int dx2 = v3.x-v2.x;
  68. int dy2 = v3.y-v2.y;
  69. int dz2 = v3.z-v2.z;
  70.  
  71. return (Math.acos(Math.abs(dx1*dx2 + dy1*dy2 + dz1*dz2) / (Math.sqrt(a2(dx1)+a2(dy1)+a2(dz1)) * Math.sqrt(a2(dx2)+a2(dy2)+a2(dz2))))/Math.PI*180);
  72. }
  73.  
  74. public static void main(String[] args) {
  75. String line;
  76. while(true){
  77. try {
  78. line = br.readLine();
  79. Scanner sc = new Scanner(line);
  80. int N = sc.nextInt();
  81. int S = sc.nextInt();
  82. int T = sc.nextInt();
  83. List<Vrchol> zoznam = new ArrayList<Vrchol>();
  84. for(int i=0; i<= N; ++i){
  85. line = br.readLine();
  86. sc = new Scanner(line);
  87. int x1 = sc.nextInt();
  88. int y1 = sc.nextInt();
  89. int z1 = sc.nextInt();
  90. Vrchol nv1 = new Vrchol(x1, y1, z1);
  91.  
  92. int x2 = sc.nextInt();
  93. int y2 = sc.nextInt();
  94. int z2 = sc.nextInt();
  95. Vrchol nv2 = new Vrchol(x2, y2, z2);
  96.  
  97. boolean jv1 = false, jv2 = false;
  98. for(Vrchol v: zoznam){
  99. if(v.equals(nv1)){
  100. nv1 = v;
  101. jv1 = true;
  102. }
  103. if(v.equals(nv2)){
  104. nv2 = v;
  105. jv2 = true;
  106. }
  107. if(jv1 && jv2){
  108. break;
  109. }
  110. }
  111.  
  112. if(!jv1) zoznam.add(nv1);
  113. if(!jv2) zoznam.add(nv2);
  114. if(i!=0){
  115. nv1.sused.add(nv2);
  116. nv2.sused.add(nv1);
  117. }
  118. }
  119.  
  120. boolean[] navstivene = new boolean[zoznam.size()];
  121. for(int i=0; i<zoznam.size(); ++i){
  122. zoznam.get(i).p=i;
  123. navstivene[i]=false;
  124. }
  125.  
  126. Vrch zac = new Vrch(0.0, zoznam.get(0), null);
  127. PriorityQueue<Vrch> fronta = new PriorityQueue<Vrch>();
  128. fronta.add(zac);
  129.  
  130. while(!fronta.isEmpty()){
  131. Vrch v = fronta.poll();
  132. //System.out.println(v.v + " " + v.d);
  133. if(navstivene[v.v.p]) continue;
  134. if(v.v.p==1) {
  135. System.out.println(v.d);
  136. break;
  137. }
  138. navstivene[v.v.p] = true;
  139. for(Vrchol sus: v.v.sused){
  140. double vz = v.d + v.v.vzdialenost(sus)/S;
  141. if(v.p!=null) vz += uhol(v.p, v.v, sus)/T;
  142. Vrch s = new Vrch(vz, sus, v.v);
  143. fronta.add(s);
  144. }
  145. }
  146.  
  147. //System.out.println(zoznam.size());
  148.  
  149. } catch (Exception e) {
  150. e.printStackTrace();
  151. return;
  152. }
  153. }
  154. }
  155. }
  156.