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; }