Under construction

Still being built. Things may change

Careful Ascent

Interview

Time limit2sMemory limit512 MB

Summary
Given a target point and vertical strips that scale horizontal speed, find the launch horizontal velocity so the craft reaches the target at vertical speed 1.
Level

Medium4 of 10

Topics
Math, Implementation, Simulation, Geometry
Solved
No attempts yet

Problem

That went well. While police sirens rang out around the palace, Mal Reynolds had already reached the lifting device he had parked outside the city.

No spaceship can leave Planet Zarzos without permission from the High Priest. Mal's spaceship, Firefly, sits in geostationary orbit well above the controlled zone, and his small lifting device is not recognised as an intruder as long as its vertical velocity is exactly 1 km/min.

Two problems remain. First, Mal cannot steer the vehicle from inside his space suit, so he has to set up the autopilot while still on the ground. The vertical velocity must be exactly 1 km/min, and the horizontal velocity must be chosen so that the resulting trajectory hits Firefly. Second, the energy shields of the planet disturb the autopilot. While the device travels through a shield, its horizontal velocity is multiplied by a given factor, and the original horizontal velocity is restored as soon as the device leaves the shield. For this problem Firefly is a single point. The shape drawn in Figure 1 is only decoration.

Figure 1: Illustration of the first example.

Mal recorded the positions of the shields and their influence on the autopilot during his descent. What he needs now is a program that tells him the right horizontal velocity setting.

Input

The input consists of:

  • One line with two integers xx and yy (−107≤x≤107-10^7 \le x \le 10^7, ∣x∣≤y≤108|x| \le y \le 10^8, 1≤y1 \le y), Firefly's coordinates relative to Mal's current position, in kilometres.
  • One line with an integer nn (0≤n≤1000 \le n \le 100), the number of shields.
  • nn lines describing the shields. Line ii contains three numbers:
    • an integer lil_i (0≤li<y0 \le l_i < y), the lower boundary of shield ii, in kilometres,
    • an integer uiu_i (li<ui≤yl_i < u_i \le y), the upper boundary of shield ii, in kilometres,
    • a real value fif_i (0.1≤fi≤10.00.1 \le f_i \le 10.0), the factor the horizontal velocity is multiplied by while the device traverses shield ii.

Shield ranges do not intersect. For every pair of shields i≠ji \ne j, either ui≤lju_i \le l_j or uj≤liu_j \le l_i holds.

Every real number has at most 10 digits after the decimal point.

Output

Print, on one line, the horizontal velocity in km/min that Mal must choose in order to reach Firefly.

Round the answer at the tenth digit after the decimal point and always print exactly nine digits after the decimal point. A value that falls exactly halfway rounds away from zero. Print a leading minus sign if the answer is negative.

Examples2

  1. Example 1

    Input
    100 140
    1
    40 90 0.2000000000
    
    Expected output
    1.000000000
    
  2. Example 2

    Input
    100 100
    3
    0 20 2.0000000000
    50 100 0.1000000000
    20 50 0.2000000000
    
    Expected output
    1.960784314