LOJ-1146 : Closest Distance

問題概要

平面上の4点A,B,C,Dが与えられる。AとCから同時に出発し、BとDに同時に到着する。途中での最短距離を求める問題。

解法

三分探索のライブラリ検証用。距離時刻に対して凸でunimordalなので適用可能。多分手で解析的に解くことも出きるはず。

acceptされたコード

#include <cstdio>
#include <cmath>
using namespace std;

int sx[2], sy[2], gx[2], gy[2];

double sq(double x) {
	return x*x;
}

double getDistance(double x1, double y1, double x2, double y2) {
	return sqrt( sq(x1 - x2) + sq(y1 - y2) );
}

double ternaryFunc(const double t) {
	return getDistance(
			sx[0] * (1.0 - t) + gx[0] * t,
			sy[0] * (1.0 - t) + gy[0] * t,
			sx[1] * (1.0 - t) + gx[1] * t,
			sy[1] * (1.0 - t) + gy[1] * t
			);
}

double findMinimal(double lower, double upper) {
	const int numIter = 100;
	for (int _ = 0; _ < numIter; ++_) {
		double middleLeft = (lower*2 + upper) / 3.0, middleRight = (lower + upper*2) / 3.0;
		if (ternaryFunc(middleLeft) < ternaryFunc(middleRight)) {
			upper = middleRight;
		}
		else {
			lower = middleLeft;
		}
	}
	return ternaryFunc(lower);
}

void init() {
	for (int i = 0; i < 2; ++i) {
		scanf("%d%d%d%d", sx+i, sy+i, gx+i, gy+i);
	}
}

double solve() {
	return findMinimal(0.0, 1.0);
}

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; ++i) {
		init();
		printf("Case %d: %.13f\n", i + 1, solve());
	}
	return 0;
}