32376번 - Draw A Perfect Circle 스페셜 저지

문제

동글이는 요즘 동그라미 챌린지를 연습 중입니다. 동그라미 챌린지란 팔을 컴퍼스처럼 휘둘러 칠판에 원을 그리는 놀이입니다.

하지만 동글이는 자신이 그린 그림이 얼마나 원에 가까운지 알기 힘들었고, 당신에게 정확도를 구하는 프로그램을 만들어줄 것을 요청했습니다.

동글이가 그린 그림은 $N$개의 점으로 표현되며, 점을 포함하는 구간의 너비인 $K$가 주어집니다.

정확도는 다음과 같은 기준으로 계산됩니다.

• 임의의 반지름 $R$에 대해, $cnt(R)$를 원점으로부터의 거리가 $\max(0,R-\frac{K}{2})$ 이상 $R+\frac{K}{2}$ 이하인 점들의 개수로 정의합니다. ($x$좌표의 차이가 $p$이고 $y$좌표의 차이가 $q$인 두 점의 거리는 $\sqrt{p^2+q^2}$ 으로 정의합니다.)
• 이때 정확도는 실수 $R$에 대해서 $\frac{100}{N}\times \max\limits_{R \ge 0} cnt(R)$ 입니다.

동글이가 완벽한 원을 그릴 수 있도록 도와주세요!

입력

첫 번째 줄에 점의 개수 $N(1\leq N \leq 200,000円)$과 너비 $K(1\leq K \leq 20,000円)$가 공백으로 구분되어 주어집니다. $N, K$는 모두 정수입니다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 점의 좌표를 나타내는 두 정수 $x_i, y_i$가 주어집니다. $(-10,000円≤x_i, y_i≤10,000円)$

모든 점의 위치는 서로 다름이 보장됩니다.

출력

동글이가 그린 그림의 정확도를 출력해주세요.

출력한 답과 정답의 절대/상대 오차가 10ドル^{-6}$ 이하이면 정답으로 인정됩니다.

제한

노트

절대오차는 정답과 출력한 답의 차이, 상대오차는 절대오차를 정답으로 나눈 값을 의미합니다.