1902번: 램프

https://www.acmicpc.net/problem/1902


$O(nC)$ // C는 삼분 검색에서 함수의 최대 호출 수

주어진 선분을 연장한 직선을 그리고 이들 중 최댓값만 취해보자. 그러면 아래로 볼록한 껍질이 그려진다.
삼분검색을 하자.

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double x[5000], y[5000], r;
double f(double t) {
        double rt = 0;
        for (int i = 1; i < n; i++)
            rt = max(rt, (y[i] - y[i - 1]) / (x[i] - x[i - 1])*(t - x[i]) + y[i]);
        return rt;
}
int main() {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%lf%lf", x + i, y + i);
        double low = x[0], up = x[n - 1], m1, m2;
        while (up - low>1e-9) {
                m1 = (low * 2 + up) / 3;
                m2 = (low + up * 2) / 3;
                f(m1) < f(m2) ? up = m2 : low = m1;
        }
        printf("%.2lf", f(m1));
        return 0;
}