아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

촛불 끄기

시간 제한4초메모리 제한512 MB

요약
반지름 R인 원판 안에 있는 점 N개를 모두 덮는 가장 좁은 띠의 너비를 구한다.
난이도

어려움10점 중 8점

유형
기하, 완전 탐색, 정렬, 분할 정복
정답자
아직 제출이 없습니다

문제

자크에두아르는 생일 케이크를 무척 좋아해서 생일을 1년마다가 아니라 1시간마다 기념한다. 친구들이 유명한 제과점에서 둥근 케이크를 주문해 윗면에 초를 꽂았다. 초의 개수는 자크에두아르의 나이를 시간으로 센 값과 같다. 그래서 케이크 윗면에는 엄청나게 많은 초가 타고 있다. 자크에두아르는 숨 한 번에 모든 초를 끄려고 한다.

초의 불꽃은 같은 평면 위의 점이고, 모두 원점을 중심으로 하고 반지름이 RR 나노미터인 원판 안에 있다. 같은 평면에서 자크에두아르가 분 바람은 폭이 WW인 직선 띠를 따라 나아간다. 이 띠는 거리가 WW만큼 떨어진 두 평행선 사이의 영역이고, 두 직선 자체도 영역에 포함된다. 방향을 가장 잘 골랐을 때 모든 초를 끌 수 있는 최소 폭 WW를 구하라.

입력

첫째 줄에 정수 NN과 RR이 공백으로 구분되어 주어진다. NN은 자크에두아르의 나이를 시간으로 센 값이다. 다음 NN개 줄에 ii번째 초의 정수 좌표 xix_i와 yiy_i가 나노미터 단위로 공백으로 구분되어 주어진다.

제한

  • 3≤N≤2×1053 \le N \le 2 \times 10^5
  • 10≤R≤2×10810 \le R \le 2 \times 10^8
  • 1≤i≤N1 \le i \le N인 모든 ii에 대해 xi2+yi2≤R2x_i^2 + y_i^2 \le R^2
  • 모든 점의 좌표는 서로 다르다.

출력

WW를 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 예를 들어 답이 2020이면 20.000000을 출력한다.

예제2

  1. 예제 1

    입력
    3 10
    0 0
    10 0
    0 10
    
    예상 출력
    7.071068
    
  2. 예제 2

    입력
    4 15
    -10 -10
    10 -10
    10 10
    -10 10
    
    예상 출력
    20.000000