ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

8680: Villages: Landcircles

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：0
提交提交记录统计Web Board

题目描述


Because of the great success of Villages: Landlines, its development team, NIO Tech, decides to develop its sequel. They call it Villages: Landcircles. In the sequel, the development team decides to use a new power system.

They change the power system from one dimension to two dimensions. In the new power system, initially there are several power stations and buildings. The goal of the game is to make every power stations and buildings connected together in the power system, forming a connected graph. Players can build some power towers and wires in the game, which are the tools to connect power stations and buildings.

Power stations or buildings can connect to power towers without wires, while power towers must connect to each other by wires. What's more, power stations and buildings can't connect to each other directly, they must connect through power towers.

Assuming that the coordinates of a building are (xi,yi)(x_i,y_i)(xi,yi) and its receiving radius is rir_iri, all the power towers whose distance from the building is no greater than rir_iri are directly connected to it without wires. That is to say, for the power tower located at (x,y)(x,y)(x,y), it is directly connected to the building at (xi,yi)(x_i,y_i)(xi,yi) without wires if and only if (x−xi)2+(y−yi)2≤ri\sqrt{(x-x_i)^2+(y-y_i)^2}\leq r_i(x−xi)2+(y−yi)2≤ri. Similarly, assuming that the power supply radius of a power station is rsr_srs, all the power towers whose distance from the power station is no more than rsr_srs are directly connected to it without wires. Supposing that the coordinates of two power towers are (xA,yA)(x_A,y_A)(xA,yA) and (xB,yB)(x_B,y_B)(xB,yB), players can connect them with the wire, and the length of wire required is (xA−xB)2+(yA−yB)2\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}(xA−xB)2+(yA−yB)2. A power tower can be connected to any number (possibly zero) of power towers, buildings and power stations.

In order to make the game more friendly to the rookies, Mocha, a member of NIO Tech, decides to develop the power distribution recommendation function. In the case of using any number of power towers, players can choose exactly one power station and several buildings to get an optimal power supply scheme, which uses the shortest total length of wires to complete the power system. However, Mocha is not sure whether her scheme is correct, so she needs your help to calculate the total length of wires used in the optimal scheme to determine the correctness of her scheme.

输入格式


The first line contains a single integer TTT (1≤T≤1031\leq T\leq 10^31≤T≤103) — the number of the test cases. For each test case:
The first line contains a single integer nnn (2≤n≤92\leq n \leq 92≤n≤9).
The second line contains three integers xs,ys,rsx_s,y_s,r_sxs,ys,rs (−2000≤xs,ys≤2000,1≤rs≤2000-2000\leq x_s,y_s\leq 2000,1\leq r_s\leq 2000−2000≤xs,ys≤2000,1≤rs≤2000) — the coordinates of the power station and its power supply radius.
The iii-th line of the next n−1n-1n−1 lines contains three integers xi,yi,rix_i,y_i,r_ixi,yi,ri (−2000≤xi,yi≤2000,1≤ri≤2000-2000\leq x_i,y_i\leq 2000,1\leq r_i\leq 2000−2000≤xi,yi≤2000,1≤ri≤2000) — the coordinates of the iii-th building and its receiving radius.
It is guaranteed that for any two distinct buildings iii and jjj, (xi−xj)2+(yi−yj)2>ri+rj\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}>r_i+r_j(xi−xj)2+(yi−yj)2>ri+rj holds. Similarly, it is guaranteed that for any building iii, (xi−xs)2+(yi−ys)2>ri+rs\sqrt{(x_i-x_s)^2+(y_i-y_s)^2}>r_i+r_s(xi−xs)2+(yi−ys)2>ri+rs holds.
It is guaranteed that there are no more than 101010 test cases with n≥8n \geq 8n≥8 in a test.

输出格式


For each test cases, print a real number in a single line, denoting the total length of wires used in the optimal scheme. Your answer will be considered correct if its relative or absolute error does not exceed 10−610^{-6}10−6.

输入样例 复制 

3
2
0 0 1
2 2 1
3
0 0 10
20 -1 1
-20 -1 1
3
0 0 1
1000 -1000 1
-1000 -1000 1

输出样例 复制 

0.82842712
18.04996879
2729.05080757

分类标签