UT Invitational Programming Contest 2019

Start

2019-05-04 20:00 CEST

UT Invitational Programming Contest 2019

End

2019-05-05 01:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -220 days 18:05:34

Time elapsed

5:00:00

Time remaining

0:00:00

Problem K
Buffon's Needle

For millenia, people have been interested in approximating $\pi $. One famous method is known as Buffon’s Needle: drop a bunch of needles of length $1$ on a coordiate plane with a vertical line drawn at each integer $x$ coordinate (so there are lines $x = 0$, $x = 1$, $x = -1$, and so on). Each needle either intersects a vertical line, or lies entirely between two vertical lines. It turns out that, if the needles are dropped randomly, the fraction of needles that intersect a vertical line can be used to approximate $\pi $! (The specific assumptions about exactly how the needles are dropped in the experiment are not important for this problem.)

In particular, let $x$ be the fraction of needles that intersect a vertical line. Then

\[ \pi \approx \frac{2}{x}. \]

You are given the positions of $N$ needles (not necessarily random), and it is guaranteed that at least one of them intersects a vertical line. What is the corresponding approximation of $\pi $, using the above formula?

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 10^4$), the number of needles. $N$ lines follow.

The $i$-th such line describes the $i$-th needle. It contains four real numbers: $x_{i1}, y_{i1}, x_{i2}, y_{i2}$. This means that the $i$-th needle has one endpoint at $(x_{i1}, y_{i1})$ in the plane and the other endpoint at $(x_{i2}, y_{i2})$.

All real numbers in the input are given with exactly $6$ digits after the decimal point and have absolute value at most $10$. Furthermore, it is guaranteed that no $x$ coordinates in the input are within $10^{-6}$ of an integer.

Since all the needles are of length $1$, for each $i$ it is guaranteed that

\[ |(x_{i1} - x_{i2})^2 + (y_{i1} - y_{i2})^2 - 1| < 10^{-3}. \]

Output

Output a single real number, the approximation of $\pi $ described above. Your answer is considered correct if its absolute or relative error is at most $10^{-6}$.

Sample Explanation

In the first sample, the first needle intersects a vertical line ($x = 1$), but the second doesn’t. So the fraction of needles that intersect vertical lines is $1/2$ and the corresponding approximation of $\pi $ is $4$.

In the second sample, both the needles intersect vertical lines ($x = 1$ and $x = 0$), so the fraction of needles that intersect vertical lines is $1$ and the corresponding approximation of $\pi $ is $2$.

Sample Input 1 Sample Output 1
2
0.500000 0.500000 1.500000 0.500000
0.400000 -0.200000 0.600000 0.779796
4.000000000000
Sample Input 2 Sample Output 2
2
0.500000 0.500000 1.500000 0.500000
2.250000 0.000000 1.542893 0.707107
2.000000000000