시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 0 0 0 0.000%

문제

A properly designed room is, as we all know, well-lit.

In keeping with the teachings of Feng Shui, you have placed a number of lamps around a newly-designed room at strategic places to give it a friendlier air.

Some of the lights project positive energy, and the rest give out only negative energy. Luckily, your neighbourhood guru knows all about this, and will gladly help you to keep the delicateenergy balance... For a small fee.

The balancing line of a particular lighting arrangement is the shortest continuous closed circuit dividing energy sources into two parts, those inside the line and those outside the line, such that the sum of energies inside and outside is equal — cancelling out any negative effects.

What is the length of this line?

입력

  • A line with one positive integer, N (2 ≤ N ≤ 12), the number of lamps.
  • N more lines, each containing three space-separated integers xi and yi (1 ≤ xi, yi ≤ 99) giving the coordinates of the ith lamp expressed in centimetres from the corner of the room, and ei (−2000 ≤ ei ≤ +2000), the energy contribution of this lamp. A lamp placed at (x, y) has a square footprint that fits inside the square with opposite corners (x − 1, y − 1) and (x + 1, y + 1) with a tiny amount of space to spare.

It is guaranteed that no two lamps will have overlapping footprints.

출력

Write one real number: the length of the shortest continuous line dividing the positive and negative energy sources in the room. Your answer should be correct up to an absolute or relative precision of 10−6.

If no such line exists, output IMPOSSIBLE instead.

예제 입력

4
10 10 5
10 20 5
20 10 5
20 20 5

예제 출력

28

예제 입력 2

4
10 10 5
10 20 1
20 10 12
20 20 8

예제 출력 2

36.2842712475

예제 입력 3

6
1 1 15
5 1 100
9 1 56
1 5 1
5 5 33
9 5 3

예제 출력 3

28.970562748

예제 입력 4

8
4 4 1
4 6 1
4 8 1
6 6 14
8 4 1
8 6 1
8 8 1
99 6 -8

예제 출력 4

32

예제 입력 5

2
4 4 2
8 8 3

예제 출력 5

IMPOSSIBLE

힌트