TopCoder SRM 662 Div2 Hard Flee

900ptでもいい気がする。
http://community.topcoder.com/stat?c=problem_statement&pm=13856

問題

二次元座標上において、プレイヤーは初期状態で原点にいる。
幾つか警備員がいる座標(X[i],Y[i])が与えられる。

プレイヤーが原点から連続した経路をたどり無限遠に移動したい。
位置Pの危険度S(P)は、そこから最寄りの警備員までの距離となる。
最適な移動法を辿る場合、経路中におけるS(P)の最小値を最大化せよ。

解法

警備員の位置は重複していることもあるので、先に重複分を削除しておく。

警備員が1名または2名の場合、原点から危険度が増さないように移動できる。
警備員を中心とし、原点を通る円をそれぞれ描いてみると、円の内部に立ち入らないように動けば原点以上に危険度が増さないことになる。
警備員が２人以下なら、どちらかの円の接線方向に動けば円の内部に立ち入らなくて済む。
よって経路における危険度は原点にいるときが最大なので、原点の危険度を答えればよい。

警備員が３名の場合、原点が警備員に囲まれていないなら、やはり危険度が増さないように移動できるので、原点の危険度が経路ちゅう最大となる。

残るケースは、警備員が３名で原点がそこに囲まれている場合である。
この場合、３点が成す三角形の３辺のどこかを横切らなければならない。
警備員からの距離を最大化するなら、当然各辺の中点のうち、距離が最大なものを選べばよい。

class Flee {
	public:
	
	bool inside(vector<int> x,vector<int> y) {
		ll a=x[0]*y[1]-x[1]*y[0];
		ll b=x[1]*y[2]-x[2]*y[1];
		ll c=x[2]*y[0]-x[0]*y[2];
		return (a*b>=0 && b*c>=0 && c*a>=0);
	}
	
	double maximalSafetyLevel(vector <int> x, vector <int> y) {
		double ret=1e10;
		int i;
		set<pair<int,int> > S;
		FOR(i,x.size()) S.insert({x[i],y[i]});
		x.clear();
		y.clear();
		FORR(r,S) x.push_back(r.first),y.push_back(r.second);
		FOR(i,x.size()) ret=min(ret,sqrt(x[i]*x[i]+y[i]*y[i]));
		
		if(x.size()==3 && inside(x,y)) {
			double ma=0;
			FOR(i,3) {
				double dx=(x[i]-x[(i+1)%3])*0.5;
				double dy=(y[i]-y[(i+1)%3])*0.5;
				ma=max(ma,sqrt(dx*dx+dy*dy));
			}
			ret=min(ret,ma);
			
		}
		return ret;
		
	}
}

まとめ

Div2 Hardにしては若干簡単。