SKIING - Alpine Skiing

no tags 

Believe it or not, the devices measuring time in alpine ski racing are not perfect. Instead of measuring the exact time, they measure an interval in which the ski racer finished the race (for example 53.42 sec - 53.45 sec).

The probability is distributed evenly on this interval. (More precisely, if we choose any two sub-intervals of equal length, the probability that the ski racer finished the race in each of these sub-intervals is equal. One can also say that each moment in the given interval has equal probability assigned to it, but this in fact says nothing since the probability for each moment is equal to zero (since there are infinitely many moments in the interval) no matter how we distribute the probability.)

And what if there are N ski racers? Then we have N intervals. Find the probability that the first ski racer on the list won the race (that is, finished the race with the minimal time).

Input

In the first line, there is an integer N (1 ≤ N ≤ 300).

In the next N lines, read the intervals assigned to the ski racers: two real numbers Ai and Bi in each line, representing the interval [Ai, Bi] of the i-th ski racer. (0 < A< B< 1000)

Output

Print the required probability. The absolute difference between yours and official solution may be at most 10-6.

Example

input

2
1.000 5.000
2.500 3.000

output

0.437500

input
4
3.500 17.300
12.700 21.200
2.900 15.000
1.000 20.000
output
0.263541

hide comments
:D: 2011-09-14 09:33:56

Yes, what's great about probabilistic problems is that you can check the values by simulation. Simply run the simulation a large number of times, count the average of value you are searching for and check if it's more or less the same than your algo's answer. That way you can see that the math really works ;)

Adrian Satja Kurdija: 2011-09-14 09:33:56

The sample case is correct. If you are skeptical about it, write a simple random algorithm to check it.

Aamir Khan: 2011-09-14 09:33:56

I think the solution for second sample input should be 0.319444
correct me if i am wrong..


Added by:Adrian Satja Kurdija
Date:2011-04-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Frane Kurtović