ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Wires

Time limit: 1.0 second
Memory limit: 64 MB
Connoisseur of sound Vova decided to update his equipment. One of the ways to improve the sound is to use point-to-point wiring with heavy wires, and the wires must be as short as possible to diminish the resistance. It is clear how to connect two terminals, it is also easy to find an optimal wiring for three terminals. But what about four terminals?
There are four terminals on a circuit board. You should connect them (there must be a contact between each pair of terminals). It is permitted to add at most three auxiliary terminals and to connect terminals with wire pieces. The goal is to minimize the total length of the wires.

Input

N is the number of tests
x1 y1  the first test
x2 y2 
x3 y3
x4 y4

x1 y1 the second test
x2 y2
x3 y3
x4 y4
…
1 ≤ N ≤ 100, xi, yi are integers, −200 ≤ xi, yi ≤ 200, no two points coincide in each test.

Output

For each test, you should output a line containing the minimal possible length of the wires. The number must be given with at least four fractional digits.

Sample

inputoutput
2
0 0
2 0
2 1
3 0

0 0
0 1
1 0
1 1
3.9093
2.7321
Problem Author: Dmitry Ivankov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1460. Wires