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.
N is the number of tests
x1 y1 the first test
x1 y1 the second test
1 ≤ N
≤ 100, xi
are integers, −200 ≤ xi
≤ 200, no two points coincide in each test.
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.
Problem Author: Dmitry Ivankov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006