文理学院程序设计在线练习


Hide from the sun

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 4   Accepted Submission(s): 3
Problem Description

Xiaoxi wants to return to the dormitory from the computer room.
The route is a straight line, some of which is directly burned by the sun, while some are in the shade.
Xiaoxi’s walking speed is 1/s, which does not cost energy.
The total length of the path is S. There are N disjoint interval (l, r), which indicated the part [l, r] are in the shade. XiaoXi starts with C unit of energy. She can cost 1 unit of energy per second to walk faster for a while, and in this case, she could get a 2/s movement speed during this time. She can also cost 3 unit of energy per second to run for a while, so that she can get 3/s of movement speed during this time.
Note: time is continuous. For example, XiaoXi can spend 2 unit energy to run for 2/3 seconds.
Xiaoxi can decide her way of moving at any time. She hopes to be exposed to the sun for the shortest time.
Input

The first line contains an integer T specifying the number of test cases.
Each test case firstly consists of a single line containing three integers S, N and C, in which s is the length of the route, and N is the number of the disjoint interval and C is the Initial energy of Xiaoxi.
The next N lines each contains two integers l and r , describe the part [l, r] is covered.

T<=1000
S, l, r, C<= 1000000000
N <= 1000
l <= r , li <=li+1

Output

Output the minimum time of which XiaoXi burned by the sun (Round to 6 decimal places)

Sample Input
3
100 0 10
100 2 20
10 20
60 100
100 1 100
0 90
Sample Output
90.000000
30.000000
3.333333
Source

2018市赛