AOJ-1127, POJ-2031 : Building a Space Station

解法

ただの最小全域木。誤差死することすらまずない親切設計な問題。

import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	class UnionFind{
		int[] pars;
		UnionFind(int n){
			pars = new int[n];
			for(int i=0; i<n; i++) pars[i] = i;
		}
		int getRoot(int x){
			return x==pars[x]?x:(pars[x] = getRoot(pars[x]));
		}
		boolean isSame(int x, int y){
			return getRoot(x) == getRoot(y);
		}
		void merge(int x, int y){
			pars[getRoot(x)] = getRoot(y);
		}
	}

	double sq(double x){ return x*x; }

	class Cell{
		double x, y, z, r;
		Cell(double _x, double _y, double _z, double _r){
			this.x = _x;
			this.y = _y;
			this.z = _z;
			this.r = _r;
		}
		double getDist(Cell a){
			return sqrt(sq(x-a.x) + sq(y-a.y) + sq(z-a.z));
		}
	}

	class Edge{
		double dist;
		int a, b;
		Edge(double _d, int _a, int _b){
			this.dist = _d;
			this.a = _a;
			this.b = _b;
		}
	}

	class Cmp implements Comparator<Edge>{
		public int compare(Edge e1, Edge e2){
			return e1.dist>e2.dist?1:e1.dist<e2.dist?-1:0;
		}
	}

	int N;
	Cell[] cells;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			N = in.nextInt();
			if(N==0) return ;
			cells = new Cell[N];
			for(int i=0; i<N; i++){
				cells[i] = new Cell(in.nextDouble(), in.nextDouble(), in.nextDouble(), in.nextDouble());
			}
			System.out.printf("%.3f\n", solve());
		}
	}


	double solve(){
		double ret = 0.0;
		UnionFind uf = new UnionFind(N);
		ArrayList<Edge> es = new ArrayList<Edge>();
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				double d = cells[i].getDist(cells[j]) - cells[i].r - cells[j].r;
				if(d <= 0) uf.merge(i, j);
				else es.add(new Edge(d, i, j));
			}
		}
		Edge[] ees = (Edge[])es.toArray(new Edge[0]);
		sort(ees, new Cmp());
		for(int i=0; i<ees.length; i++){
			if(!uf.isSame(ees[i].a, ees[i].b)){
				uf.merge(ees[i].a, ees[i].b);
				ret += ees[i].dist;
			}
		}
		return ret;
	}

	public static void main(String args[]){
		new Main().run();
	}
}