핫스팟 timer 3s memory 512MB

핫스팟이란 인터넷 사업자가 제공하는 라우터를 가지고 무선 랜 (Wireless Local-Area Network, WLAN)을 설치하여 사람들이 Wi-Fi를 쓸 수 있게 만든 장소를 뜻한다. 일반인들은 핫스팟을 보통 “Wi-Fi 핫스팟”이라고 부른다. 공용 핫스팟은 보통 AP (Wireless Access Point)라고 부르는 무선 기지국을 통하여 만들어진다. 기지국의 세기가 r (음이 아닌 정수) 이라면 기지국으로부터 거리가 r 이하인 영역에서 Wi-Fi가 터진다. 기지국의 핫스팟은 기지국을 중심으로 하고 반지름이 r 인 원이다.

KOI 시에는 길다란 가로수길이 있다. 지금은 가로수길 위에 기지국 몇 개가 이미 세워져 있다. KOI 시에서는 아직 기지국의 세기를 정하지 못했는데 이는 기지국의 세기를 정하는 데 규칙이 있기 때문이다. 임의의 기지국 두 개를 선택하더라도 두 기지국의 핫스팟이 겹치면 안 된다. 단, 두 핫스팟이 경계선에서만 만나는 것은 허용된다. 특별한 경우로 기지국의 세기가 0일 때가 있다. 이럴 때는 세기가 0인 기지국이 다른 기지국의 핫스팟 안에 있으면 안 되며, 기지국이 다른 기지국의 핫스팟 경계선에 있는 것은 허용된다.

KOI 시에서는 Wi-Fi가 터지는 영역이 최대한 넓도록 기지국의 세기를 적절히 정하려고 한다. Wi-Fi가 터지는 영역은 기지국의 세기의 제곱의 합에 원주율(π)을 곱한 값이다. 목표를 달성하기 위해 일부 기지국의 세기를 0으로 설정해도 된다.

가로수길은 평면 위의 직선으로 생각할 수 있고, 기지국은 직선 위의 점으로 생각할 수 있다. n 개의 기지국이 주어지면, Wi-Fi가 터지는 영역의 넓이를 최대화시키는 프로그램을 작성하여라. 그 과정에서 당연히 두 기지국의 핫스팟이 겹치면 안된다.

예를 들어 위 그림같이 기지국이 0, 2, 5에 있다고 해보자. 파란색 원과 같이 각 기지국의 반경을 1, 1, 2로 설정하면 Wi-Fi가 터지는 영역은 총 6π 이다. 만약 빨간색 원과 같이 각 기지국의 반경은 2, 0, 3으로 설정하면 Wi-Fi가 터지는 영역은 총 13π이며 이보다 더 넓은 영역을 사용하는 방법은 없다.