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.

Under two situations the player could score one point.

⋅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);
}
}

最新文章

  1. 在Winform程序中设置管理员权限及为用户组添加写入权限
  2. delphi里动态创建AlphaControls实现换肤
  3. 使用Android Studio搭建Android集成开发环境
  4. 2、网页制作Dreamweaver(图片热点、frameset框架)
  5. VC编译错误:一个或多个多重定义的符号
  6. linux下C++对线程的封装
  7. cookie记录用户的浏览商品的路径
  8. Web API CSRF保护实现
  9. NOIP2018旅行
  10. node os模块
  11. Vijos1910 NOIP2014提高组 Day2T3 解方程 其他
  12. 指针delete之后赋值为null
  13. RNA Sequencing
  14. python---redis管道(事务)和发布订阅
  15. linux下主流的三种远程技术
  16. 前端 HTML 常用标签 head标签相关内容
  17. Base64加密解密工具类
  18. 使用gdb调试
  19. 20155336虎光元实验四 Android开发基础
  20. Red Hat系统安装Redis

热门文章

  1. &lt;一&gt;面向对象分析之面向对象和面向过程
  2. Delphi ORD
  3. RegExp类型和text()方法
  4. java正则表达式Pattern和Matcher
  5. 基于Dubbo框架构建分布式服务
  6. Metaspace 之一--java8 去掉 perm 用 Metaspace 来替代
  7. 自定义TreeList单元格 z
  8. DateTime日期计算
  9. C++实现网格水印之调试笔记(五)—— 提取出错
  10. DX11&amp;C++