BOULDER - Move the boulder

no tags 

A huge boulder is somehow blocking a public square. The citizens, each one of them approaching from his/her street, decide to remove it. Each citizen can try to either push the boulder away from him, pull it towards him, or choose to do nothing. (note that the citizens cannot change their direction relative to the boulder). Obviously, they want to remove the boulder as quickly as possible - in other words, they want to maximise the magnitude of the net force they apply. Tell them what this maximum possible magnitude is.

Input

The first line contains T (1≤T≤15), the number of test cases.

For each test case, the first line contains N (1 ≤ N ≤ 105), the number of citizens. Each of the next N lines contains four integers (separated by single spaces) :

  • The first two integers (each ≤ 109) represent the x and y components (respectively) of the direction in which the citizen would push. If he pulls, it would be in the exactly opposite direction. Note that this given "direction vector" does not necessarily have magnitude 1. However, its magnitude is indeed a meaningless quantity.
  • The next two integers Fpull and Fpush (1 ≤ Fpull, Fpush ≤ 105) represent the magnitude of the force the citizen applies while pulling and pushing, respectively.

Output

For each test case, output a single decimal number, correct to 6 digits after the decimal point, representing the maximum possible magnitude of resultant force.

Example

Input:
2
3
1 0 5 3
-3 0 12 6
0 1 4 7
1
13 6 58 24

Output:
16.5529
58

hide comments
Oleg: 2023-11-14 02:25:20

See also: https://www.spoj.com/problems/MVECTOR/ that needs exactly same algo.

David: 2021-03-18 19:51:05

The output says "correct to 6 digits after the decimal point". Therefore, the output for test case 1 should read "16.552945".


Added by:Anil Shanbhag
Date:2013-01-15
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET