奥赛一本通 1438 灯泡

1438 灯泡

题目大意

灯泡照射人的影子落在地上与墙壁上，人可以在灯泡与墙壁间移动，求影子的最大长度。

H
h
D

知识要点

函数、三分

解题思路 1

假设人与灯的水平距离为 $x$，那么光线倾角的正切值为 $\\frac{H-h}{x}$，如果影子全落在地面上则长度为 $\\frac{hx}{H-h}$。若落在墙上，则那一部分长度为 $h-\\frac{(D-x)(H-h)}{x}$。即影子的总长度满足$$L=\\begin{cases} \\frac{hx}{H-h}, & \\frac{hx}{H-h} \\lt D-x, \\\\ D-x+h-\\frac{(D-x)(H-h)}{x}, & \\frac{hx}{H-h} \\ge D-x \\end{cases}$$

这个分段函数由一次函数与对勾函数组成，必然是一个单峰函数，可以使用三分法求最值。

参考代码 1

#include <bits/stdc++.h>
using namespace std;

double H, h, D;
double L(double x) {
if(h * x / (H – h) < D – x) return h * x / (H – h);
else return D – x + h – (H – h) * (D – x) / x ;
}
int main() {
int t;
scanf("%d", &t);
while(t—) {
scanf("%lf%lf%lf", &H, &h, &D);
double l = 0, r = D, m1, m2;
while(r – l > 1e-9) {
m1 = l + (r – l) / 3, m2 = r – (r – l) / 3;
if(L(m1) < L(m2)) l = m1;
else r = m2;
}
printf("%.3lf\\n", L(l));
}
return 0;
}

解题思路 2

$$L=\\begin{cases} \\frac{hx}{H-h}, & 0 \\le x \\lt D (1 – \\frac{h}{H}), \\\\ D+H-x-\\frac{D(H-h)}{x} , & D (1 – \\frac{h}{H}) \\le x \\le D \\end{cases}$$

第一段是递增的一次函数，由于函数是连续的，最大值必然在第二段，而第二段对勾函数的极值点为 $x_0=\\sqrt{D(H-h)}$，对应函数值为 $D+H-2x_0$，区间两端点的函数值分别为 $\\frac{Dh}{H}$ 与 $h$。

参考代码 2

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
double H, h, D, x, ans;
scanf("%d", &t);
while(t—) {
scanf("%lf%lf%lf", &H, &h, &D);
x = sqrt(D * (H – h));
if(D * (1 – h / H) <= x && x <= D) ans = D + H – 2 * x;
else ans = max(h, D * h / H);
printf("%.3lf\\n", ans);
}
return 0;
}