Problem F
Hidden Triangles
Input: Standard Input
Output: Standard Output
|
|
|
Figure 1: |
When consecutive lattice points along x-axis are connected with consecutive lattice points of another row above it, several triangles are formed as shown in Figure 1. Lattice points, are the points in two-dimensional coordinate system whose abscissa and ordinate has integer values. For example (3, 4) is a lattice point but (3, 4.5) is not a lattice point. Consecutive lattice points of a row means the lattice points whose y-coordinate value is same but whose x-coordinate value is consecutive. Such a group of lattice points can be specified by specifying only the x-coordinate of the left most point and x-coordinate of the rightmost point. So to describe a system of points in two rows, five integers are enough. Let’s say these integers are x1down, x2down, x1up, x2up and h. Where x1down and x2down are the x-coordinates of leftmost and rightmost points on x-axis respectively, h is the distance between x-axis and the row above it. x1up and x2up are the x-coordinates of leftmost and right most points of the row above. All points on x-axis are connected with all points on the row above it via an straight line segment. After connecting these points many triangles is formed whose base is the x-axis and height is less than h. In the figure-1 x1down=5, x2down=8, x1up=5 and x2up=7 and h=1 and there 18 such triangles are formed.
If x1down=0, x2down=2, x1up=0 and x2up=2 and h=1 then nine such triangles are formed.. All these triangles are filled black in Figure 2.
|
|
|
|
|
|
|
|
|
|
|
|
|
Figure 2: Formed nine triangles are shown by filling them with black. |
||
When number of lattice points on the lines are very small, then such triangles are very easy to count, but for large number of lattice points such triangles are hard to count, let alone measuring the average height of such triangles.
In this problem you have to do this mammoth task. Given the values of x1down, x2down, x1up, x2up and h your job is to find the average height of all the triangles formed whose base is x-axis and height is less than h.
Input
The input file contains at most 5001 lines of inputs. Each line contains five integer numbers x1down, x2down (0≤x1down<x2down≤100000 and |x1down-x2down|≤10000), x1up, x2up (0≤x1up<x2up≤100000 and |x1up-x2up|≤10000) and h (0<h≤10).
Input is terminated by a line containing five zeroes.
Output
For each line of input produce one line of output. This line contains the serial of output followed by a floating-point number which denotes the average height of the formed triangles. The floating point number should have six digits after the decimal point. Errors less than 1.5*10-6.will be ignored. Look at the output for sample input for details.
Sample Input Output for Sample Input
|
5 8 5 7 1 0 2 0 2 1 0 100 0 101 1 0 0 0 0 0 |
Case 1: 0.542593 Case 2: 0.500000 Case 3: 0.498223
|
Problemsetter: Shahriar Manzoor
Special Thanks: Derek Kisman