import java.io.*; import java.util.*; import java.text.DecimalFormat; // 円を表すデータ構造 class Circle { public double r, x, y; public double dist( Circle c ) { return Math.sqrt( (x-c.x)*(x-c.x) + (y-c.y)*(y-c.y) ) - r - c.r; } public static Circle readFromSt(StreamTokenizer st) throws IOException { Circle c = new Circle(); st.nextToken(); c.r = st.nval; st.nextToken(); c.x = st.nval; st.nextToken(); c.y = st.nval; return c; } } // Circle[] のソート用比較関数(x座標順) class CmpX implements Comparator { public int compare(Object lhs, Object rhs) { double lv = ((Circle) lhs).x; double rv = ((Circle) rhs).x; return lvrv ? 1 : 0; } } // Circle[] のソート用比較関数(y座標順) class CmpY implements Comparator { public int compare(Object lhs, Object rhs) { double lv = ((Circle) lhs).y; double rv = ((Circle) rhs).y; return lvrv ? 1 : 0; } } // メインルーチン public class circle_inaba { // main : 入力を読んでsolveを呼んで返値を表示するだけ public static void main( String[] arg ) throws Exception { DecimalFormat fmt = new DecimalFormat("0.00000000"); StreamTokenizer st = new StreamTokenizer( new BufferedReader( new InputStreamReader(System.in))); while( st.nextToken() == StreamTokenizer.TT_NUMBER ) { int n = (int) st.nval; if( n == 0 ) break; Circle[] cs = new Circle[n]; for(int i=0; i 0.0 : "non-overlapping"; return d; } // 4個より大きいときは、分割統治。 // まず、配列を真ん中で左右に分ける :: cs_x[b..m) と cs_x[m..e)。 // 直線 centerX の左右に分ける、と言ってもよい。 int m = (b+e)/2; double centerX = (cs_x[m-1].x + cs_x[m].x) / 2; // 左右それぞれの最近円対距離を計算して、短い方を覚えておく :: d // 完全2分割しながら再帰しているので、再帰の深さは log_2(N) である。 double d = Math.min( closest(cs_x, b, m, R), closest(cs_x, m, e, R) ); // さて、すると、全体 cs_x[b..e) の最近円対距離は // d // であるか、または // centerXの近く(左側)にある円とcenterXの近く(右側)にある円との距離 // であるか、どちらかである。 // なので、まずは centerX の近くにある円をとりあえず集めてみる :: cs_y // 「近く」はどのくらい近ければいいかというと、d+2*R くらい近ければよい。 // これ以上遠いと、中心が反対側にある円との距離が明らかにd以上になるので。 Circle[] cs_y = new Circle[e-b]; int NN = 0; for(int i=b; i 0.0 : "non-overlapping"; return d; } }