D. Max and Bike
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/595/problem/D
Description
For months Maxim has been coming to work on his favorite bicycle. And quite recently he decided that he is ready to take part in a cyclists' competitions.
He knows that this year n competitions will take place. During the i-th competition the participant must as quickly as possible complete a ride along a straight line from point si to point fi (si < fi).
Measuring time is a complex process related to usage of a special sensor and a time counter. Think of the front wheel of a bicycle as a circle of radius r. Let's neglect the thickness of a tire, the size of the sensor, and all physical effects. The sensor is placed on the rim of the wheel, that is, on some fixed point on a circle of radius r. After that the counter moves just like the chosen point of the circle, i.e. moves forward and rotates around the center of the circle.
At the beginning each participant can choose any point bi, such that his bike is fully behind the starting line, that is, bi < si - r. After that, he starts the movement, instantly accelerates to his maximum speed and at time tsi, when the coordinate of the sensor is equal to the coordinate of the start, the time counter starts. The cyclist makes a complete ride, moving with his maximum speed and at the moment the sensor's coordinate is equal to the coordinate of the finish (moment of time tfi), the time counter deactivates and records the final time. Thus, the counter records that the participant made a complete ride in time tfi - tsi.
Maxim is good at math and he suspects that the total result doesn't only depend on his maximum speed v, but also on his choice of the initial point bi. Now Maxim is asking you to calculate for each of n competitions the minimum possible time that can be measured by the time counter. The radius of the wheel of his bike is equal to r.
⋅1. If you touch a buoy before your opponent, you will get one point. For example if your opponent touch the buoy #2 before you after start, he will score one point. So when you touch the buoy #2, you won't get any point. Meanwhile, you cannot touch buoy #3 or any other buoys before touching the buoy #2.
⋅2. Ignoring the buoys and relying on dogfighting to get point.
If you and your opponent meet in the same position, you can try to
fight with your opponent to score one point. For the proposal of game
balance, two players are not allowed to fight before buoy #2 is touched by anybody.
There are three types of players.
Speeder:
As a player specializing in high speed movement, he/she tries to avoid
dogfighting while attempting to gain points by touching buoys.
Fighter:
As a player specializing in dogfighting, he/she always tries to fight
with the opponent to score points. Since a fighter is slower than a
speeder, it's difficult for him/her to score points by touching buoys
when the opponent is a speeder.
All-Rounder: A balanced player between Fighter and Speeder.
There will be a training match between Asuka (All-Rounder) and Shion (Speeder).
Since the match is only a training match, the rules are simplified: the game will end after the buoy #1 is touched by anybody. Shion is a speed lover, and his strategy is very simple: touch buoy #2,#3,#4,#1 along the shortest path.
Asuka is good at dogfighting, so she will always score one point by dogfighting with Shion, and the opponent will be stunned for T seconds after dogfighting.
Since Asuka is slower than Shion, she decides to fight with Shion for
only one time during the match. It is also assumed that if Asuka and
Shion touch the buoy in the same time, the point will be given to Asuka
and Asuka could also fight with Shion at the buoy. We assume that in
such scenario, the dogfighting must happen after the buoy is touched by
Asuka or Shion.
The speed of Asuka is V1 m/s. The speed of Shion is V2 m/s. Is there any possibility for Asuka to win the match (to have higher score)?
Input
The first line contains three integers n, r and v (1 ≤ n ≤ 100 000, 1 ≤ r, v ≤ 109) — the number of competitions, the radius of the front wheel of Max's bike and his maximum speed, respectively.
Next n lines contain the descriptions of the contests. The i-th line contains two integers si and fi (1 ≤ si < fi ≤ 109) — the coordinate of the start and the coordinate of the finish on the i-th competition.
Output
Print n real numbers, the i-th number should be equal to the minimum possible time measured by the time counter. Your answer will be considered correct if its absolute or relative error will not exceed 10 - 6.
Namely: let's assume that your answer equals a, and the answer of the jury is b. The checker program will consider your answer correct if .
Sample Input
2 1 2
1 10
5 9
Sample Output
3.849644710502
1.106060157705
HINT
题意
有一个*，*上的一点，要从f滚到s
你可以随意选择一开始*的点在哪儿
然后问你最少多少时间
题解：
我们二分时间，如果 v*t + dis >= f-s就好了
v*t表示*中心所能位移的路径。
dis是*上面的点所能走的距离，我们可以通过贪心得到的，首先我们可以通过t，得到这个点究竟转过了多少的角度
要让*上的点走的最远，我们肯定是让他通过对称的方式走，所以可以算出一个最长距离
然后check就好了
代码
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std; const double pi = acos(-1.0);
int t;double r,v,f,s;
int check(double t)
{
double dis = v * t;
double len = fmod(dis,*pi*r);
double k = len / r / 2.0;
double dis2 = 2.0 * abs(sin(k)) * r;
if(dis + dis2 > f-s)return ;
return ;
}
int main()
{
scanf("%d",&t);
cin>>r>>v;
while(t--)
{
scanf("%lf%lf",&s,&f);
double l=0.0,r=1999999999.0;
for(int i=;i<;i++)
{
double mid=(l+r)/2.0;
if(check(mid))r=mid;
else l=mid;
}
printf("%.15f\n",l);
}
}