24554번 - 불협화음 스페셜 저지

pichulia 는 혼자서 음악을 듣곤 한다. 그러던 중, 불현듯 동그라미와 각진 세모가 등장하는 문제를 만들고 싶어졌다!

2차원 평면상에 반지름이 $R$로 똑같이 생긴 원 $N$개가 있다. pichulia 는 여기서 하나의 각진 정삼각형을 그려서, 그것을 “작품”이라고 부르고 싶다.

pichulia 가 그린 정삼각형이 “작품”이 되기 위해선 아래의 두 조건을 모두 만족해야 한다.

• 어떠한 원의 경계선 또는 일부도 정삼각형 외부에 있어서는 안 된다.
• 정삼각형의 각 변은 최소 1개의 원과 접해야 한다. (동그라미와 세모는 친구이기 때문이다!)

“작품”이 될 수 있는 가장 작은 정삼각형의 한 변의 길이와, 가장 큰 정삼각형의 한 변의 길이를 각각 구해보자.

첫 번째 줄에는 원의 개수 $N$과 원의 반지름 $R$이 주어진다. ($1 \le N \le 10^5$, $1 \le R \le 1\,000$)

이후 두 번째 줄부터 $N+1$ 번째 줄까지 $N$줄에 걸쳐서 각 원의 중심의 좌표 값을 나타내는 두 정수 $X_i$, $Y_i$가 공백을 사이에 두고 주어진다. ($-10^{8} \le X_i$, $Y_i \le 10^{8}$)

입력으로 주어지는 모든 수는 정수다.

첫째 줄에는 “작품”이 될 수 있는 가장 작은 정삼각형의 한 변의 길이를 출력한다.

둘째 줄에는 “작품”이 될 수 있는 가장 큰 정삼각형의 한 변의 길이를 출력한다.

출력한 값과 정답과의 절대 오차 또는 상대 오차가 $10^{-7}$ 이하여야 한다.

허용 오차가 매우 작으므로 실수 연산의 오차를 주의하자.