National Olympiad in Informatics, China, 2004

Day 2, Problem 1 - Rainfall

Country M has a very wet climate, especially in city P. Frequent precipitation brings forth many troubles for its people. To make crossing the road easier on rainy days, the government has installed a device known as the "automatic umbrella" above every crosswalk in the city (depicted in figure 1).

Figure 1

Each automatic umbrella can be seen as a rectangle-shaped board of an irrelevant thickness. These type of umbrellas are exceptional at absorbing water. Rainwater that lands on the umbrella will be completely sucked up by little holes on its up surface and transported away using pipes. When it is not raining, these umbrellas are idle. Once it rains, they will immediately begin to move back and forth in a linear path with constant speed - that is, from one side of the road to the other side with uniform motion, then returning to the first side with the same speed, and so forth until the rain ends. At no given time will the umbrella move beyond the boundaries of the road. With these automatic umbrellas, pedestrians without an umbrella of their own will be able walk underneath them during rainy days and avoid getting wet.

Due to the limited sizes of automatic umbrellas, one is clearly not enough when there are a lot of people trying to use them to cross the road. So, the government has installed multiple automatic umbrellas at various major intersections. Each umbrella's width is equal to the width of the crosswalk, however, their heights are all unique, and they may not necessarily share the same lengths or speeds.

Given the status of a particular crosswalk, please calculate the total volume of water that has landed on the ground of the crosswalk, T seconds after it has started to rain.

Input Format

The first line contains four integers N, W, T, and V. N represents the number of automatic umbrellas, W represents the width of the crosswalk, T represents the time elapsed since it started to rain, and V represents the volume of rainfall per unit area per unit time.

To better explain this, figure 2 depicts a side view of 5 automatic umbrellas in action on a Cartesian plane, where the left border of the road is the origin, right is in the positive x direction, and up is in the positive y direction. This way, each automatic umbrella can be viewed as a line segment on the Cartesian plane.

Figure 2

In the following N lines, each line consists of three integers describing a single automatic umbrella. The first integer x describes its initial location, representing the position of its leftmost side on the horizontal axis. The second integer l is the length of umbrella along the positive x direction. The third integer v is the speed of the umbrella, where the size of v represents the rate at which it moves. If v > 0, then the umbrella is initially moving towards the right; if v < 0, then the umbrella is initially moving towards the left; if v = 0, then the umbrella does not move.

Output Format

The output should contain one line with one real number, representing the total volume of water that has landed on the ground of the crosswalk, T seconds after it started to rain. The answer must be rounded and displayed to two decimal places.


  • Rain drops will fall straight down, landing uniformly amongst the ground at a uniform rate.
  • The surfaces of automatic umbrellas are parallel to the ground.
  • The widths of automatic umbrellas and the crosswalk are the same, all equaling 1.
  • N ≤ 10
  • W ≤ 100
  • T ≤ 100
  • V ≤ 50
  • The total number of back and forth cycles for all the umbrellas will not exceed 250. Moving from one side to the other and back counts as one cycle.

Sample Input

2 4 3 10
0 1 1
3 1 -1

Sample Output


All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 19, 2014

Languages Allowed:

Comments (Search)

It's quiet in here...