0부터 n-1까지 n명의 참가자의 달리기 속도와 자전거 속도가 주어진다.

전체 길이가 t킬로미터인데

n-1 참가자가 자신이 승리할 수 있도록 달리기와 자전거 경주의 길이를 조정해달라고 뇌물 먹였다.

이 참가자가 2등과 가장 큰 차이로 우승하려면 달리기 경주의 길이 r과 자전거 경주의 길이 t-r을 어떻게 설정해야 할까?

구하려고 하는 것 : others(r) - cheaters(r) 의 최대치

others 는 이렇게 생겼다.

각 x위치에서의 최소치를 고르면 그림 (b)의 저런 함수가 나온다.

(참고로, 선형 함수 여러 개의 최소치를 나타내는 함수는 항상 위로 볼록한 형태이다.)

others(r) - cheaters(r) 의 최대치도 오목 함수이다.

• 볼록 함수와 볼록 함수를 더한 결과도 볼록 함수이다.
• 선형 함수는 볼록 함수이기도, 오목 함수이기도 하다.

double t;
vector<double> runSpeed, cycleSpeed
// 달리기 구간의 길이가 run일 때, i번 선수가 걸리는 시간
double time(int i, double run)
{
	double cycle = t - run;
	return run / runSpeed[i] + cycle / cycleSpeed[i];
}
// 달리기 구간 길이가 r일 때, others(r)-cheater(r)를 반환한다.
double diff(double r)
{
	int n = runSpeed.size();
	double cheater = time(n - 1, r);
	double others = time(0, r);
	for (int i = 1; i < n - 1; ++i)
	{
		others = min(others, time(i, r));
	}
	return others - cheater;
}
// diff() 함수의 최대치의 위치를 삼분 검색으로 계산한다.
double maxDifference()
{
	double lo = 0, hi = t;
	for (int it = 0; it < 100; ++it)
	{
		double aab = (2 * lo + hi) / 3;
		double abb = (lo + 2 * hi) / 3;
		if (diff(aab) > diff(abb)
			hi = abb;
		else
			lo = aab;
	}
	return (lo + hi) / 2;
}