SRM 235 DIV1 Hard RemoteRover

問題 Editorial

問題

水平の境目で分割された領域がいくつかある。
それぞれの領域は幅がwidth[i]で、speed[i]の速度を出すことができる。
(0, 0)から(offset, sum width)まで行くとき、時間を最小化せよ

解答

それぞれの領域ではspeed[i]に比例する傾き(cosθ)で行けばいい。
なぜかはわかってないが、そうらしい。
あとは比例の係数を求めたいが、二分探索でいい

コード

#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(o) (o).begin(), (o).end()
using namespace std;
typedef long double ld;
struct RemoteRover {
	double optimalTravel(vector <int> width, vector <int> speed, int offset) {
		int n = width.size();
		ld l = 0, u = 1.L / *max_element(all(speed));
		ld d;
		rep(ii, 100) {
			ld m = (l+u)/2;
			ld x = 0; d = 0;
			rep(i, n) {
				ld s = acos(speed[i] * m);
				x += width[i] / tan(s);
				d += width[i] / sin(s) / speed[i];
			}
			if(x > offset) u = m;
			else l = m;
		}
		return d;
	}
};