Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.util.Arrays;
- import java.util.PriorityQueue;
- import java.util.StringTokenizer;
- public class Spantree implements Runnable {
- private String nextToken() {
- if (st == null || !st.hasMoreTokens()) {
- try {
- st = new StringTokenizer(in.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- private int nextInt() {
- return new Integer(nextToken());
- }
- private long nextLong() {
- return new Long(nextToken());
- }
- private class Pair implements Comparable<Pair> {
- public int v;
- public int d;
- public Pair(int v, int d) {
- this.v = v;
- this.d = d;
- }
- @Override
- public int compareTo(Pair o) {
- return this.d - o.d;
- }
- }
- private StringTokenizer st;
- private BufferedReader in;
- private BufferedWriter out;
- class Point implements Comparable<Point> {
- public double x;
- public double y;
- public double dist;
- public int num;
- public Point(int x, int y, int num) {
- super();
- this.x = x;
- this.y = y;
- this.num = num;
- }
- public Point(Point p, double dist) {
- this.x = p.x;
- this.y = p.y;
- this.num = p.num;
- this.dist = dist;
- }
- @Override
- public int compareTo(Point arg0) {
- return (int) (this.dist - arg0.dist);
- }
- }
- private double dist(Point a, Point b) {
- return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- @Override
- public void run() {
- try {
- in = new BufferedReader(new FileReader("spantree.in"));
- out = new BufferedWriter(new FileWriter("spantree.out"));
- int N = nextInt();
- Point[] point = new Point[N];
- double[] dist = new double[N];
- Arrays.fill(dist, Double.MAX_VALUE);
- boolean used[] = new boolean[N];
- for (int i = 0; i < N; i++) {
- point[i] = new Point(nextInt(), nextInt(), i);
- }
- dist[0] = 0;
- double sum = 0;
- for (int i = 0; i < N; i++) {
- int min = 0;
- for (int j = 0; j < N; j++) {
- if (!used[j] && (used[min] || (dist[j] < dist[min]))) {
- min = j;
- }
- }
- used[min] = true;
- sum += dist[min];
- for(int j=0; j<N; j++){
- if(!used[j] && dist(point[min],point[j]) < dist[j]){
- dist[j] = dist(point[min],point[j]);
- }
- }
- }
- out.write(sum + "\n");
- in.close();
- out.close();
- } catch (Exception e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- public static void main(String[] args) {
- new Thread(new Spantree()).start();
- }
- }
Add Comment
Please, Sign In to add comment