Codeforces #409 Div1 B. Volatile Kite

誤差死した問題。
http://codeforces.com/contest/800/problem/B

問題

二次元座標系で凸図形が与えられる。
各頂点を最大Dだけ任意方向に移動したとしても、図形が凸であるようなDの上限を求めよ。

解法

二分探索で解く。
今図形中の連続する3点を時計回りにA-B-Cとする。この場合、BはベクトルACに対し左側にある。
Dだけ各頂点が移動してもこの関係が崩れないためには、Bから直線ACに下ろした垂線の長さが2D以上であればよい。

自分は最初垂線の長さをベクトルの内積から求めたら誤差のためかpretestが通らなかった。
三角形ABCの符号付面積を求めて、底辺|AC|を割ることで高さを求める方だとうまく通った。

int N;
ll X[1010],Y[1010];
long double D[1010][1010];

long double dist(int a,int b,int c) {
	double AX=X[a]-X[b];
	double AY=Y[a]-Y[b];
	double BX=X[c]-X[b];
	double BY=Y[c]-Y[b];
	double A=abs(AX*BY-AY*BX)/2.0;
	double H=2*A/D[c][b];
	return H;
}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N;
	
	FOR(i,N) cin>>X[i]>>Y[i];
	long double MD=1e10;
	FOR(x,N) FOR(y,N) D[x][y]=hypot(X[x]-X[y],Y[x]-Y[y]);
	FOR(y,N) FOR(x,y) MD=min(MD,D[x][y]/2.0);
	FOR(x,N) MD=min(MD,dist((x+1)%N,x,(x+2)%N)/2.0);
	
	_P("%.12lf\n",(double)MD);
	
}

まとめ

今まで内積を使った垂線の長さの求め方で失敗したことなかったでこれは意外。
今後は面積を使う方法に切り替えようかな。