(5/5)

Story

Your employees have too many mangos. The mangos go bad after some time and leave a sticky, smelly residue. The park is beginning to look and smell like a pig sty every day. Luckily, you have intercepted the communications with the local mango providers and your employees. Now you know in advance when the mangos arrive for the next year. Additionally, you can estimate when each shipment spoils based on the provider.

Your animals can consume food at a constant, non-negative, real rate (in pounds per minute). The more animals you have the higher this rate, but the more it will cost to maintain the park. Your objective is to find out the smallest rate at which the animals need to be able to consume food such that no amount of mango spoils in the upcoming year. You can assume that if there are no mangos in your park, then the animals will instead eat some of the other non-perishable food your park has.

Problem

Given the shipment description of all the mangos (arrival time, spoil time, and size in pounds). Determine the smallest rate the animals in your park can consume food such that none of the mangos spoil.

Input

Input will begin with a line containing 1 integer, n (1 ≤ n ≤ 200,000), representing the number of shipments of mangos. The following n lines will contain the description of a single mango shipment. The mango shipment description will consist of a line with 3 integers, Ta, Ts, and S (1 ≤ Ta < Ts ≤ 525,600; 1 ≤ S ≤ 2,000), representing the arrival time, the spoil time, and the size in pounds of the shipment respectively. Note the shipments are not guaranteed to be in their arrival order.

Output

Output a single line that contains a single non-negative real number representing the rate (in pounds per minute) that your animals need to consume food.

Your answer will be accepted if it is within 10-5 absolute or relative error. For example if the answer is 2,000,000, then an acceptable answer would be in the range of 1,999,980 to 2,000,020. Additionally, if the answer is 0.25, then an acceptable answer would be in the range, 0.24999 to 0.25001

Sample Input Sample Output

5 2.000000

15 20 5

5 10 10

13 20 4

27 48 2

21 100 6

3 1.285714

1 4 3

3 6 3

5 8 3

Explanation

Case 1

We have 5 shipments. In terms of arrival we have the following situation.

● The first shipment arrives at time 5 and spoils 5 times units later (time 10); it has 10 pounds of mangos.

● The second shipment arrives at time 13 and spoils 7 time units later (time 20); it has 4 pounds of mangos.

● The third shipment arrives at time 15 and spoils 5 time units later (time 20); it has 5 pounds of mangos.

● The fourth shipment arrives at time 21 and spoils 79 time units later (time 100); it has 6 pounds of mangos.

● The fifth shipment arrives at time 27 and spoils 21 time units later (time 48); it has 2 pounds of mangos.

A rate of 2 pounds per time unit can allow for us to

● Finish the first shipment just as it spoils.

● Finish the second shipment at time 15

● Finish the third shipment at time 17.5

● Finish the fourth shipment at time 24

● Finish the fifth shipment at time 28

Any rate less than 2 would not work since the first shipment would expire

Case 2

There are 3 shipments.

● The first shipment arrives at times 1 and spoils 3 time units later; it has 3 pounds of mangos

● The second shipment arrives at time 3 and spoils 3 time units later; it has 3 pounds of mangos

● The third shipment arrives at time 5 and spoils 3 time units later; it also has 3 pounds of mangos

At a rate of 9/7 we can

● Finish the first shipment at time 3⅓

● Finish the second shipment at time 5⅔

● Finish the third shipment at time 8 (when it spoils).

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Get Free Quote!

437 Experts Online