Guest User

Untitled

a guest
Jul 18th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.67 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.FileReader;
  4. import java.io.FileWriter;
  5. import java.io.IOException;
  6. import java.util.Arrays;
  7. import java.util.PriorityQueue;
  8. import java.util.StringTokenizer;
  9.  
  10. public class Spantree implements Runnable {
  11.  
  12. private String nextToken() {
  13. if (st == null || !st.hasMoreTokens()) {
  14. try {
  15. st = new StringTokenizer(in.readLine());
  16. } catch (IOException e) {
  17. e.printStackTrace();
  18. }
  19. }
  20. return st.nextToken();
  21. }
  22.  
  23. private int nextInt() {
  24. return new Integer(nextToken());
  25. }
  26.  
  27. private long nextLong() {
  28. return new Long(nextToken());
  29. }
  30.  
  31. private class Pair implements Comparable<Pair> {
  32. public int v;
  33. public int d;
  34.  
  35. public Pair(int v, int d) {
  36. this.v = v;
  37. this.d = d;
  38. }
  39.  
  40. @Override
  41. public int compareTo(Pair o) {
  42. return this.d - o.d;
  43. }
  44.  
  45. }
  46.  
  47. private StringTokenizer st;
  48. private BufferedReader in;
  49. private BufferedWriter out;
  50.  
  51. class Point implements Comparable<Point> {
  52. public double x;
  53. public double y;
  54.  
  55. public double dist;
  56. public int num;
  57.  
  58. public Point(int x, int y, int num) {
  59. super();
  60. this.x = x;
  61. this.y = y;
  62. this.num = num;
  63. }
  64.  
  65. public Point(Point p, double dist) {
  66. this.x = p.x;
  67. this.y = p.y;
  68. this.num = p.num;
  69. this.dist = dist;
  70. }
  71.  
  72. @Override
  73. public int compareTo(Point arg0) {
  74. return (int) (this.dist - arg0.dist);
  75. }
  76.  
  77. }
  78.  
  79. private double dist(Point a, Point b) {
  80. return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  81. }
  82.  
  83. @Override
  84. public void run() {
  85. try {
  86. in = new BufferedReader(new FileReader("spantree.in"));
  87. out = new BufferedWriter(new FileWriter("spantree.out"));
  88.  
  89. int N = nextInt();
  90. Point[] point = new Point[N];
  91. double[] dist = new double[N];
  92. Arrays.fill(dist, Double.MAX_VALUE);
  93. boolean used[] = new boolean[N];
  94.  
  95. for (int i = 0; i < N; i++) {
  96. point[i] = new Point(nextInt(), nextInt(), i);
  97. }
  98.  
  99. dist[0] = 0;
  100.  
  101. double sum = 0;
  102.  
  103. for (int i = 0; i < N; i++) {
  104. int min = 0;
  105.  
  106. for (int j = 0; j < N; j++) {
  107. if (!used[j] && (used[min] || (dist[j] < dist[min]))) {
  108. min = j;
  109. }
  110. }
  111.  
  112. used[min] = true;
  113. sum += dist[min];
  114.  
  115. for(int j=0; j<N; j++){
  116. if(!used[j] && dist(point[min],point[j]) < dist[j]){
  117. dist[j] = dist(point[min],point[j]);
  118. }
  119. }
  120.  
  121. }
  122.  
  123. out.write(sum + "\n");
  124.  
  125. in.close();
  126. out.close();
  127. } catch (Exception e) {
  128. // TODO Auto-generated catch block
  129. e.printStackTrace();
  130. }
  131. }
  132.  
  133. public static void main(String[] args) {
  134. new Thread(new Spantree()).start();
  135. }
  136.  
  137. }
Add Comment
Please, Sign In to add comment