[UVA][二分搜] 10372 - Leaps Tall Buildings
Problem A: Leaps Tall Buildings (in a single bound)
It's a bird! It's a plane! It's coming right at us!
Although it sometimes seems like it, Superman can't fly (without a plane). Instead, he makes super-human leaps, especially over tall buildings. Since he never knows when he will need to catch a criminal, he can't register flight paths. To avoid hitting planes, he tries to keep his jumps as low to the ground as he can. Given a city-scape as input, find the angle and velocity of Superman's jump that minimizes his maximum altitude.
Recall that gravity provides an acceleration of 9.8 m/s2 downwards and the formula for Superman's vertical distance from his starting location is d(t)=v t + 0.5 a t2 where v is his initial velocity, a is his acceleration and t is time in seconds since the start of the leap.
Input:
Input consists of a sequence of city-scapes, each of the form
n
0 d1
h2 d2
:
h(n-1) d(n-1)
0 dn
Superman starts at ground level and leaps d1+...+dn metres, landing at ground level and clearing all of the buildings at heights h2 to h(n-1), each with the given widths. n will be at most 100.
Output:
Output is the angle and initial velocity that minimizes the height that Superman attains, both appearing on the same line. The values should be given to two decimal places and be accurate within 0.01 degrees or m/s, as appropriate.
Sample Input:
3 0 5 10 5 0 5 5 0 10.5 20 11.5 25 10 10 15 0 7
Diagram for Second City-scape
(Not to scale.)
Sample Output:
71.57 15.65 67.07 27.16
題目描述：
水平上有很多建築物，求一條角度最小的拋物線抵達指定位置，並且途中不能撞到建築物。
題目解法：
Vx = Vcos(theta), Vy = Vsin(theta)
水平位移 X = sigma(di), 初速度 V, 總時間 t
=> Vx t = X => t = X/Vx
y(t) = y(0) + Vy t - 0.5*9.8*t*t => t = 2Vy/9.8
V = sqrt(x*9.8 / (2 cos(theta)*sin(theta))) = sqrt(x*9.8 / sin(2*theta))
對 角度 二分搜尋，檢查是否有撞到建築物。
#include <stdio.h>
#include <math.h>
using namespace std;
#define eps 1e-8
int check(int n, double h[], double d[], double theta, double v) {
double vx = v*cos(theta), vy = v*sin(theta);
double t, x = 0, hh;
int i;
for(i = 0; i < n; i++) {
t = x/vx;
hh = vy*t - 0.5*9.8*t*t;
if(hh < h[i]-eps)
return 0;
t = (x+d[i])/vx;
hh = vy*t - 0.5*9.8*t*t;
if(hh < h[i]-eps)
return 0;
x += d[i];
}
return 1;
}
int main() {
int n, i;
double h[105], d[105];
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%lf %lf", &h[i], &d[i]);
double X = 0;
for(i = 0; i < n; i++)
X += d[i];
double l = 0, r = acos(-1)/2, mid;//binary search
double theta, v;
while(fabs(l-r) > 1e-5) {
mid = (l+r)/2;
theta = mid, v = sqrt(X*9.8/sin(2*theta));
if(check(n, h, d, theta, v))
r = mid;
else
l = mid;
}
printf("%.2lf %.2lf\n", theta/acos(-1)*180, v);
}
return 0;
}