ACPC 2020 - Division 1


2020-11-14 10:00 AKST

ACPC 2020 - Division 1


2020-11-14 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -10 days 18:18:28

Time elapsed


Time remaining


Problem C
Wormhole Extreme!!!

Brad and Joseph are planning a new science fiction series called Wormhole Extreme!!! where explorers journey about the galaxy by traversing wormholes. As with many science fiction series, the laws of physics are given a creative reinterpretation for the purpose of entertainment.

  • A wormhole can be thought of as a straight line connecting its two openings. The ship travels along this line while it is in the wormhole.

  • The explorers enter the wormhole with some initial velocity and then the spacecraft is ballistic: the spacecraft’s controls are inoperable while flying in the wormhole. But some unknown wormhole force affects the spacecraft’s velocity while in the wormhole.

More precisely, the wormhole can be thought of as consecutive intervals where interval $i$ has length $\ell _ i$ wormhole units ($\omega $). While the spacecraft is travelling along interval $i$, its acceleration is $a_ i$ wormhole units per second squared ($\omega / s^2$). So velocities are simply scalar values indicating the speed in which the ship is approaching the exit. Negative velocities indicate the ship is actually flying back towards the entrance. When the ship transitions from one interval to the next, its velocity is preserved during this transition. Note, $a_ i$ could be either positive (the ship accelerates in this segment) or negative (the ship decelerates in this segment) but wormhole physics dictate it will never be zero.

The crew needs to enter the wormhole with a large enough initial velocity or else they could get pushed back to the entrance. To increase tension, Brad and Joseph want to calculate the minimum possible nonnegative velocity $v$ such that if the spacecraft has velocity $v$ at the entrance of the wormhole, then it will reach the exit. Given this velocity, they also want to know how long it will take the spacecraft to reach the exit.


  • If the spacecraft reaches the start of an interval $i$ the moment its velocity becomes 0 and if $a_ i > 0$, the spacecraft immediately begins to accelerate and its journey continues.

  • This also applies to the initial segment $i = 1$: a spacecraft with velocity $0$ at the entrance will immediately start journeying through the wormhole if $a_1 > 0$.

  • Similarly, if the spacecraft reaches the exit the moment its velocity reaches $0$, it successfully exits the wormhole because the crew can resume operation of the craft.


Input begins with a single integer $N$ ($1 \leq N \leq 100\, 000$). Then $N$ lines follow where line $i$ contains two integers $d_ i, a_ i$ ($1 \leq d_ i \leq 10\, 000$ and $-100 \leq a-i \leq 100$, $a_ i \neq 0$) indicating the $i$’th segment of the wormhole has distance $d_ i~ \omega $ and acceleration $a_ i~ \omega /s^2$. The total length of all segments will be at most $100\, 000$.


Output consists of a single line with two real values $V$ and $T$ separated by a single space. Here, $V \geq 0$ is the minimum nonnegative value such that if the spacecraft enters the wormhole with velocity $V$ then it will escape and $T$ is the time it will take for the spacecraft to exit the wormhole if it enters with velocity $V$. Of course, $V$ should be reported in $\omega /s^2$ and $T$ in seconds.

The output will be accepted if both output values are within an absolute or relative error of $10^{-3}$ of their respective correct values.

Sample Input 1 Sample Output 1
10 -2
6.3245553203 3.1622776180
Sample Input 2 Sample Output 2
10 1
10 -2
4.4721359550 5.0146969659
Sample Input 3 Sample Output 3
5 2
20 1
40 -3
30 -2
17.3205080757 9.5194371919
Sample Input 4 Sample Output 4
10000 1
0.0000000000 141.4213562373