Build Fences

Winter is coming , chicks are preparing building fences to protect from cold wind.
They are going to use the limited fences to surround some trees , they will either make some trees out of the fences or leave them inside[the first image, OK].

They won't make the fences touch trees outside and the fences should always be tighten.[the second image, forbidden]

(touch: two things have one or more points in common.)
Also , they want their living space as large as possible ,only the light blue districts are their living space.
The trees' coordinates and their radius are given. No trees will touch each other.
You can use a fence whose length is L , what's the largest area the chicks can live?

T(<=20) in the first line indicating case number.
For each case, n(1<=n<=16) , d(0<d<=1000) , L(0<=L<=1000000).
d : diameter of the trees , float number.
L : length of the fence , float number.
The next n lines each has two float numbers, x(|x|<=1000) , y(|y|<=1000) , which are the coodinates of the trees' center.

Tell the chicks what's their largest possible living space accurate to three decimal places.

2

1 1 1
1 1

4 1 30
1 1
4 4
1 4
4 1

0.000
12.644

MadFroG

HDOJ Monthly Contest – 2010.04.04