Encircling Circles
Encircling Circles
You are given a set of circles C of a variety of radii (radiuses) placed at a variety of positions, possibly overlapping one another. Given a circle with radius r, that circle may be placed so that it encircles all of the circles in the set C if r is large enough.
There may be more than one possible position of the circle of radius r to encircle all the member circles of C. We de ne the region U as the union of the areas of encircling circles at all such positions. In other words, for each point in U, there exists a circle of radius r that encircles that point and all the members of C. Your task is to calculate the length of the periphery of that region U.
Figure 1. shows an example of the set of circles C and the region U. In the gure, three circles contained in C are expressed by circles of solid circumference, some possible positions of the encircling circles are expressed by circles of dashed circumference, and the area U is expressed by a thick dashed closed curve.
Figure 1. Example of the Circle Set
Input data
The input is a sequence of datasets. The number of datasets is less than 100.
Each dataset is formatted as follows.
n rx_1 y_1 r_1x_2 y_2 r_2...x_n y_n r_n
The first line of a dataset contains two positive integers, n and r, separated by a single space. n means the number of the circles in the set C and does not exceed 100. r means the radius of the encircling circle and does not exceed 1000.
Each of the n lines following the rst line contains three integers separated by a single space. (x_i, y_i) means the center position of the i^th circle of the set C and r_i means its radius.
You may assume -500 ≤ x_i ≤ 500, -500 ≤ y_i ≤ 500, and 1 ≤ r_i ≤ 500.
The end of the input is indicated by a line containing two zeros separated by a single space.
Output data
For each dataset, output a line containing a decimal fraction which means the length of the periphery (circumferential length) of the region U.
The output should not contain an error greater than 0.01. You can assume that, when r changes by ϵ (|ϵ| < 0.0000001), the length of the periphery of the region U will not change more than 0.001.
If r is too small to cover all of the circles in C, output a line containing only 0.0.
No other characters should be contained in the output.
Figure 2. Last Dataset of the Sample Input
Examples
1 10 5 5 7 2 12 5 5 7 8 6 3 3 10 3 11 2 2 1 1 2 16 3 3 15 -5 2 5 9 2 9 5 8 6 3 38 -25 -10 8 30 5 7 -3 35 11 3 39 -25 -10 8 30 5 7 -3 35 11 3 800 -400 400 2 300 300 1 300 302 1 3 800 400 -400 2 300 300 1 307 300 3 8 147 130 80 12 130 -40 12 -110 80 12 -110 -40 12 70 140 12 70 -100 12 -50 140 12 -50 -100 12 3 493 345 154 10 291 111 75 -275 -301 46 4 55 54 0 1 40 30 5 27 36 10 0 48 7 3 30 0 3 3 -3 0 4 400 0 3 3 7 2 3 2 -5 -4 2 -4 3 2 3 10 -5 -4 5 2 3 5 -4 3 5 4 6 4 6 1 5 5 1 1 7 1 0 1 1 3 493 345 154 10 291 111 75 -275 -301 46 5 20 -9 12 5 0 15 5 3 -3 3 12 9 5 -12 9 5 0 0
81.68140899333463 106.81415022205297 74.11215318612639 108.92086846105579 0.0 254.85616536128433 8576.936716409238 8569.462129048667 929.1977057481128 4181.124698202453 505.09134735536804 0.0 46.82023824234038 65.66979416387915 50.990642291793506 4181.124698202453 158.87951420768937