2149 Inherit the Spheres

「2149 Inherit the Spheres」の編集履歴(バックアップ)一覧はこちら

2149 Inherit the Spheres」(2006/04/17 (月) 02:18:56) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2149 Inherit the Spheres **問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=2149 **解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0) break; Sphere[] sph = new Sphere[n]; for(int i=0;i<n;i++){ sph[i] = new Sphere (sc.nextDouble(),sc.nextDouble(),sc.nextDouble(),sc.nextDouble()); } TreeSet<ActionPoint> act = new TreeSet<ActionPoint>(); findActionPoint1(n, sph, act); findActionPoint2(n, sph, act); Vector<Integer> output = new Vector<Integer>(); boolean[] exist = new boolean[n]; boolean[][] connect = new boolean[n][n]; for(int i=0;i<n;i++) exist[i] = false; for(int i=0;i<n;i++) for(int j=0;j<n;j++) connect[i][j] = false; int prev = 0; for(ActionPoint a:act){ int s = a.s; if(a.type == ActionPoint.GENERATE){ exist[s] = true; for(int t:a.connectv){ connect[s][t] = true; connect[t][s] = true; } } else if(a.type == ActionPoint.UNGENERATE){ exist[s] = false; for(int i=0;i<n;i++){ connect[i][s] = false; connect[s][i] = false; } } else if(a.type == ActionPoint.CONNECT){ int t = a.connect; connect[s][t] = true; connect[t][s] = true; } else if(a.type == ActionPoint.UNCONNECT){ int t = a.connect; connect[s][t] = false; connect[t][s] = false; } int cnt = count(n,exist,connect); //System.out.println("cnt:"+cnt); if(prev>cnt) output.add(0); else if(prev<cnt) output.add(1); prev = cnt; } System.out.println(output.size()); for(int b:output){ System.out.print(b); } System.out.println(); } } private static int count(int n, boolean[] exist, boolean[][] connect){ int cnt = 0; boolean[] searched = new boolean[n]; for(int i=0;i<n;i++) searched[i] = false; for(int i=0;i<n;i++){ if(exist[i]&&!searched[i]){ search(n,connect,searched,i); cnt++; } } return cnt; } private static void search(int n,boolean[][] connect,boolean[] searched,int k){ searched[k] = true; for(int i=0;i<n;i++){ if(connect[k][i]&&!searched[i]) search(n,connect,searched,i); } } private static void findActionPoint1(int n, Sphere[] sph, TreeSet<ActionPoint> act) { for(int i=0;i<n;i++){ Sphere s = sph[i]; ActionPoint gen = new ActionPoint(ActionPoint.GENERATE,i,s.z-s.r); ActionPoint ungen = new ActionPoint(ActionPoint.UNGENERATE,i,s.z+s.r); for(int j=0;j<n;j++){ if(i==j) continue; if(s.bottomContained(sph[j])){ gen.connectv.add(j); } } act.add(gen); act.add(ungen); } } private static void findActionPoint2(int n, Sphere[] sph, TreeSet<ActionPoint> act) { for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ double d = sph[i].dist(sph[j]); if(d==0) continue; if(d>=sph[i].r+sph[j].r) continue; double z0,z1,r0,r1; if(sph[i].z<=sph[j].z){ z0 = sph[i].z; z1 = sph[j].z; r0 = sph[i].r; r1 = sph[j].r; } else{ z0 = sph[j].z; z1 = sph[i].z; r0 = sph[j].r; r1 = sph[i].r; } double t = z1-z0; double dx = sph[i].x-sph[j].x; double dy = sph[i].y-sph[j].y; double s = Math.sqrt(dx*dx+dy*dy); double d0 = (d+(r0*r0-r1*r1)/d)*0.5; double x = Math.sqrt(r0*r0-d0*d0); double zplus = d0*t/d + x*s/d + z0; double zminus = d0*t/d - x*s/d + z0; if(!sph[i].topContained(sph[j]) && !sph[j].topContained(sph[i])){ ActionPoint a = new ActionPoint(ActionPoint.UNCONNECT,i,zplus,j); act.add(a); } if(!sph[i].bottomContained(sph[j]) && !sph[j].bottomContained(sph[i])){ ActionPoint a = new ActionPoint(ActionPoint.CONNECT,i,zminus,j); act.add(a); } } } } } class ActionPoint implements Comparable<ActionPoint>{ static final int GENERATE = 0; static final int UNGENERATE = 1; static final int CONNECT = 2; static final int UNCONNECT = 3; int type; int s; double z; int connect; Vector<Integer> connectv; public boolean equals(Object o){ ActionPoint a = (ActionPoint)o; return this.z==a.z; } public int compareTo(ActionPoint a){ if(this.z-a.z>0) return 1; else if(this.z-a.z<0) return -1; else return 0; } ActionPoint(int type, int s, double z) { this.type = type; this.s = s; this.z = z; this.connect = -1; this.connectv = new Vector<Integer>(); } ActionPoint(int type, int s, double z,int connect) { this.type = type; this.s = s; this.z = z; this.connect = connect; this.connectv = null; } } class Sphere{ double x; double y; double z; double r; Sphere(double x, double y, double z, double r) { this.x = x; this.y = y; this.z = z; this.r = r; } public boolean bottomContained(Sphere s){ double dx = this.x-s.x; double dy = this.y-s.y; double dz = (this.z-this.r)-s.z; double d = Math.sqrt(dx*dx+dy*dy+dz*dz); return d<=s.r; } public boolean topContained(Sphere s){ double dx = this.x-s.x; double dy = this.y-s.y; double dz = (this.z+this.r)-s.z; double d = Math.sqrt(dx*dx+dy*dy+dz*dz); return d<=s.r; } public double dist(Sphere s){ double dx = this.x-s.x; double dy = this.y-s.y; double dz = this.z-s.z; double d = Math.sqrt(dx*dx+dy*dy+dz*dz); return d; } }

表示オプション

横に並べて表示:
変化行の前後のみ表示:
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。