20. Archery

Problem Statement:
Last summer you were watching all the matches in the 2012 Olympics in London. One of the interesting sports is archery (it's the game of propelling arrows with the use of a bow to hit a target), but in this problem we are dealing with a new type of archery.

In this new type of archery, the player has arrows that can penetrate any target and can go to infinity (the same arrow may hit more than one target), and there will be a lot of targets around the player everywhere, and the targets may intersect and/or overlap with each others.

From the top view you can model the targets as line segments and the player as a point at the origin (point (0,0) is the origin), also there will be no target which intersects with the player's position.

You are really interested to calculate the expected number of targets this player can penetrate using one arrow, if he will shoot his arrow in a random direction (there are infinite number of different directions, and each direction has the same probability to be used for the random shoot).

For example, the following figure explains the first sample test case, where the player is at the origin, and there are two targets T1 with end points (1,5) and (3,3), and T2 with end points (3,5) and (6,2), you can notice that there is a region where the player can shoot an arrow and penetrate the two targets, and there are two regions where he can penetrate only one target, and the last region he will not penetrate any target.

Note that a target can be hit at any point between its 2 end points (inclusive).

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by the test cases, each test case starts with a line containing one integer N (1 ≤ N ≤ 100) representing the number of targets in the game. Followed by N lines, the i-th line contains 4 integers separated by a single space X1 Y1 X2 Y2 (−100 ≤ X1, Y1, X2, Y2 ≤ 100) representing the i-th target end points (X1, Y1) and (X2, Y2)

Output Format:
For each test case, print on a single line, a single number representing the expected number of targets the player can penetrate using one arrow, rounded to five decimal places.

Sample Input:
2 2 1 5 3 3 3 5 6 2 8 3 0 0 3 0 3 -3 0 -3 0 0 -3 0 -3 3 0 3 3 -3 3 -3 3 -3 -3 -3 -3 3 -3 3 -3 3 3

Sample Output:
0.20636 2.00000

 Added by: abdelkarim Added at: 2014-02-22 20:17:13 UTC Time Limit: 3 seconds Partial score: No Source: ACM Arab Collegiate Programming Contest 2012