Space Golf
题目连接：
http://codeforces.com/gym/100803/attachments
Description
You surely have never heard of this new planet surface exploration scheme, as it is being carried
out in a project with utmost secrecy. The scheme is expected to cut costs of conventional rovertype
mobile explorers considerably, using projected-type equipment nicknamed “observation
bullets”.
Bullets do not have any active mobile abilities of their own, which is the main reason of their
cost-efficiency. Each of the bullets, after being shot out on a launcher given its initial velocity,
makes a parabolic trajectory until it touches down. It bounces on the surface and makes another
parabolic trajectory. This will be repeated virtually infinitely.
We want each of the bullets to bounce precisely at the respective spot of interest on the planet
surface, adjusting its initial velocity. A variety of sensors in the bullet can gather valuable data
at this instant of bounce, and send them to the observation base. Although this may sound like
a conventional target shooting practice, there are several issues that make the problem more
difficult.
• There may be some obstacles between the launcher and the target spot. The obstacles
stand upright and are very thin that we can ignore their widths. Once the bullet touches
any of the obstacles, we cannot be sure of its trajectory thereafter. So we have to plan
launches to avoid these obstacles.
• Launching the bullet almost vertically in a speed high enough, we can easily make it hit
the target without touching any of the obstacles, but giving a high initial speed is energyconsuming.
Energy is extremely precious in space exploration, and the initial speed of the
bullet should be minimized. Making the bullet bounce a number of times may make the
bullet reach the target with lower initial speed.
• The bullet should bounce, however, no more than a given number of times. Although
the body of the bullet is made strong enough, some of the sensors inside may not stand
repetitive shocks. The allowed numbers of bounces vary on the type of the observation
bullets.
You are summoned engineering assistance to this project to author a smart program that tells
the minimum required initial speed of the bullet to accomplish the mission.
Figure D.1 gives a sketch of a situation, roughly corresponding to the situation of the Sample
Input 4 given below
Input
You can assume the following.
• The atmosphere of the planet is so thin that atmospheric resistance can be ignored.
• The planet is large enough so that its surface can be approximated to be a completely flat
plane.
• The gravity acceleration can be approximated to be constant up to the highest points a
bullet can reach.
These mean that the bullets fly along a perfect parabolic trajectory.
You can also assume the following.
• The surface of the planet and the bullets are made so hard that bounces can be approximated
as elastic collisions. In other words, loss of kinetic energy on bounces can be ignored.
As we can also ignore the atmospheric resistance, the velocity of a bullet immediately after
a bounce is equal to the velocity immediately after its launch.
• The bullets are made compact enough to ignore their sizes.
• The launcher is also built compact enough to ignore its height.
You, a programming genius, may not be an expert in physics. Let us review basics of rigid-body
dynamics.
• The horizontal velocity component of the bullet is kept constant during its flight when
atmospheric resistance is ignored. Thus the horizontal distance from the launcher is proportional
to the time elapsed.
• The vertical velocity component vy is gradually decelerated by the gravity. With the
gravity acceleration of g, the following differential equation holds during the flight.
dvy
Solving this with the initial conditions of vy = viy and y = 0 when t = 0, we obtain the
following.
The equation (4) tells that the bullet reaches the ground again when t = 2viy/g. Thus, the
distance of the point of the bounce from the launcher is 2vixviy/g. In other words, to make
the bullet fly the distance of l, the two components of the initial velocity should satisfy
2vixviy = lg.
• Eliminating the parameter t from the simultaneous equations above, we obtain the following
equation that describes the parabolic trajectory of the bullet.
For ease of computation, a special unit system is used in this project, according to which the
gravity acceleration g of the planet is exactly 1.0.
Output
The input consists of a single test case with the following format.
d n b
p1 h1
p2 h2
.
.
.
pn hn
The first line contains three integers, d, n, and b. Here, d is the distance from the launcher
to the target spot (1 ≤ d ≤ 10000), n is the number of obstacles (1 ≤ n ≤ 10), and b is the
maximum number of bounces allowed, not including the bounce at the target spot (0 ≤ b ≤ 15).
Each of the following n lines has two integers. In the k-th line, pk is the position of the k-th
obstacle, its distance from the launcher, and hk is its height from the ground level. You can
assume that 0 < p1, pk < pk+1 for k = 1, . . . , n − 1, and pn < d. You can also assume that
1 ≤ hk ≤ 10000 for k = 1, . . . , n.
Sample Input
343 3 2
56 42
190 27
286 34
Sample Output
11.08710
Hint
题意
你需要从(0,0)点扔出去一个球，恰好扔在(d,0)
而且这个球不能碰到任何一个障碍，最多在地上弹b次
问你速度最小为多少
题解：
我们可以物理一点去想，这个抛物线一定是靠着某一个障碍或者45°扔出去的
所以我们直接暴力枚举靠在哪一个障碍就好了
我们处理的时候，可以优化一下，可以直接把抛物线变成关于y轴对称的抛物线，然后把障碍都移到那儿
然后再判断
注意：精度有毒
代码
#include<bits/stdc++.h>
using namespace std;
double d;
int n,b;
double p[20],h[20];
double eps = 1e-6;
double solve(int t)
{
double dis = d/t;
double p2[20],h2[20];
for(int i=1;i<=n;i++)
{
p2[i]=p[i];
while(p2[i]>=dis)
p2[i]-=dis;
p2[i]-=dis/2.0;
h2[i]=h[i];
}
double ans = 1e9;
for(int i=1;i<=n;i++)
{
double A = h2[i]/(p2[i]*p2[i]-dis*dis/4);
double C = -A*dis*dis/4.0;
double vy = sqrt(2*C);
double vx = dis/(2*vy);
double v = sqrt(vx*vx+vy*vy);
int flag = 1;
for(int j=1;j<=n;j++)
{
double H = A * p2[j] * p2[j] + C;
if(h2[j]-H>eps)
{
flag = 0;
break;
}
}
if(flag)
{
ans = min(ans,v);
}
}
double v = sqrt(dis);
double C = dis/4;
double A = -1/dis;
int flag = 1;
for(int i=1;i<=n;i++)
{
double H = A * p2[i] * p2[i] + C;
if(h2[i]-H>eps)
{
flag = 0;
break;
}
}
if(flag)
ans = min(ans,v);
//cout<<ans<<" "<<v<<endl;
return ans;
}
int main()
{
scanf("%lf%d%d",&d,&n,&b);
b++;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i],&h[i]);
double v = 1e9;
for(int i=1;i<=b;i++)
v=min(v,solve(i));
printf("%.10f\n",v);
}