Official
B - 友好の印 / Sign of Friendship Editorial by en_translator
When there are a single obstacle, the slope of the line through the UFO and the top of the obstacle is \(\frac{H-h}{D-d}\), so the minimum height you have to climb is \(\max\bigl(0, h - d \times \frac{H-h}{D-d}\bigr)\).
When there are multiple obstacles, the answer will be the maximum value of \(\max\bigl(0, h - d \times \frac{H-h_i}{D-d_i}\bigr)\).
Sample Code (C++)
#include <iostream>
using namespace std;
void chmax(double& a, double b){ if(a < b) a = b; }
int main(){
int N;
double D, H, ans = 0;
cin >> N >> D >> H;
while(N--){
double d, h;
cin >> d >> h;
chmax(ans, h - d * (H - h) / (D - d));
}
cout << ans << endl;
}
Sample Code (Python)
N, D, H = map(int, input().split())
ans = 0.0
for i in range(N):
d, h = map(int, input().split())
h -= d * (H - h) / (D - d)
if ans < h:
ans = h
print(ans)
posted:
last update: