1288번 - 전쟁 - 국지전

전쟁은 점점 고조되어서 국지전의 형태를 띄게 되었다. 요컨데, 여러 부근 부근에서 자잘한 전투가 계속 일어나게 된다는 것이다.

당신은 지금 국지전이 일어나고 있는 전장을 바라보고 있다. 그런데, 만약 국지전의 이길 가능성이 낮다 라면 모든 군대를 일단 회군시키고자 한다.

이길 가능성을 계산하는 방법은 다음과 같다.

n개의 군대가 있으면, 어떤 지역은 그 곳과 가장 가까운 군대에 귀속된다. 귀속된 땅의 크기가 곧 이길 확률이 되는데, 당신은 이길 확률이 얼마나 될지 알아보고 싶기 때문에 자신의 군대가 지배한 땅의 면적을 알고 싶다.

한 부대는 하나의 점으로 표현된다. 예를 들자면, 이런 소리다.

이런 모습으로 군대가 배치되어 있다면 아래와  같이 땅을 각각의 군대가 지배하게 된다.

그러면 저 면적들을 구해 각각의 국가마다 더하면 답을 구할 수 있을 것이다.

다음은 예제의 그림이다.

첫째 줄에 군대의 수 N과(1 ≤ N ≤ 100) 현재 전장의 크기인 x가 주어진다.(1 ≤ x ≤ 10,000) (전장은 (0,0)~(x,x)이다.) 두 번째 줄에서 N+1번째 줄에는 각각 군사의 위치 (a,b)와 그 군대의 국가 c가 0또는 1로 주어진다. (c = 0이면 당신의 군대고, c = 1이면 적의 군대이다.) 입력은 모두 정수이다.

당신 나라의 병사들이 지배한 땅의 면적과 적나라의 병사들이 지배한 땅의 면적을 한 줄에 “%.1lf” 의 형식으로 각각 출력한다.