問題概要
二次元空間上に $N$ 個の点がある．$i$ 番目の点の座標は $( x_i, y_i )$ である．
ここで，正の実数 $r$ を一つ決めて，位置 $( -10^9, 0 )$ に半径 $r$ の円を置く．その後，この円を位置 $( 10^9, 0 )$ に（連続的に）移動させる．このとき，$N$ 個の点及び， 2 つの直線 $y = 100$, $y = -100$ が円内部に含まれる瞬間があってはならない．
そのようなことが可能な $r$ の最大値はいくらか？
制約
- $1 \leq N \leq 100$
- $| x_i |, | y_i | \leq 100$
- 点の座標は相異なる
解法
ある実数 $r$ について valid な移動経路が存在したとします．このとき，$r$ より小さい任意の正の実数についても valid な移動経路が存在します．逆に，ある実数 $r$ について valid な移動経路が存在しないとき，$r$ より大きな任意の正の実数についても valid な移動経路は存在しません．よって，valid な移動経路が存在するか否かというのは $r$ に関して単調性をもちます．従って，$r$ に関する二分法を考えることができます*1．
ということで，ある実数 $r$ を固定したときに，valid な移動経路が存在するかどうかを判定する問題について考えます．まず分かることとして，ある 2 点 $i, j$ 間の距離 $d = \sqrt{ ( x_i - x_j )^2 + ( y_i - y_j )^2 }$ が $d > r$ を満たすとき，この 2 点間を通り抜けることができず，$d \leq r$ ならば通り抜けることができます．直線と点の間についても，直線の内で最も点に近い点*2との距離を $d$ として同じようなことが言えます．これで，与えられた点たち（と 2 直線）を普通に二次元に描画したときに，通り抜けられない 2 点間（または直線と点の間）を線分で結んだ図というのを考えることができるようになりました（通れないところに壁を置いていくイメージ）．作図が面倒なので各自脳内で描いてください．そのような図において，（円を移動させる問題の）valid な移動経路というのは，（今描いた図で）線分に接触せずに（面積 $0$ の）点を移動させる移動経路に対応しています．これはつまり，位置 $( -10^9, 0 )$ から $( 10^9, 0 )$ へ通り抜ける隙間があるかどうかということですが，見方を変えれば，完全に塞いでいる部分があるかどうかということになります．もう少し言い方を変えれば，先程描いた図において，直線 $y = 100$ から 直線 $y = -100$ へ，線分を辿って到達できるならば完全に塞いでいる箇所が存在し，そうでないならば隙間があります．この連結性の判定は，$N$ 点と直線を頂点・先程描いた線分を辺としたグラフにおける連結性と同じことなので，素集合データ構造や DFS などを用いて連結性を判定すれば，$r$ を固定したときの判定問題を解くことができ，二分法で答えが求まります．
この解放の場合，二分法の試行回数は double 型の仮数部の精度だけあればよく，定数回の反復で終れます．各反復では $\Theta( N^2 )$ 頂点のグラフについての連結性判定を解きますが，素集合データ構造を使うと $O( N^2 \alpha( N )$ 時間になります（$\alpha$ はいつものアッカーマン関数の逆関数的なやつです）．反復回数は定数回だったので，全体でも $O( N^2 \alpha( N )$ 時間となります．
コード
#include <complex> using Point = complex< double >; constexpr double EPS = 1e-8; constexpr double PI = acos( -1 ); constexpr Point O( 0, 0 ); // 入力ストリームから実数二つをとって Point へ istream& operator>> ( istream &s, Point &a ) { double r, i; s >> r >> i; a = Point( r, i ); return s; } // 外積（クロス積） double cross( const Point &a, const Point &b ) { return a.real() * b.imag() - a.imag() * b.real(); } // 点 p と直線 ( q1, q2 ) の距離 // include : cross double distancePL( const Point &p, const Point &q1, const Point &q2 ) { return abs( cross( q2 - q1, p - q1 ) ) / abs( ( q2 - q1 ) ); } class DisjointSetForest; // DisjointSetForest( N ) // find( x ) // same( x, y ) // unite( x, y ) // groups() // groupSize( x ) bool check( const VT< Point > &ps, const double R ) { const int N = SZ( ps ); DisjointSetForest dsf( N + 2 ); REP( i, N ) { if ( distancePL( ps[i], Point( 0, 100 ), Point( 100, 100 ) ) + EPS < R ) { dsf.unite( i, N ); } if ( distancePL( ps[i], Point( 0, -100 ), Point( 100, -100 ) ) + EPS < R ) { dsf.unite( i, N + 1 ); } REP( j, i ) { if ( abs( ps[i] - ps[j] ) + EPS < R ) { dsf.unite( i, j ); } } } return !dsf.same( N, N + 1 ); } int main() { IN( int, N ); VT< Point > ps( N ); for_each( ALL( ps ), []( auto &p ){ cin >> p; } ); double lb = 0, ub = 201; REP( 64 ) { const double mid = ( lb + ub ) / 2; ( check( ps, mid ) ? lb : ub ) = mid; } cout << lb / 2 << endl; return 0; }
