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

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

직선

면접 대비

시간 제한1초메모리 제한128 MB

요약
고정된 점 P를 지나는 직선 중 주어진 n개 점까지의 거리 중 최댓값을 가장 작게 만드는 직선을 찾고, 그 최솟값을 소수 셋째 자리에서 버림하여 출력한다.
난이도

보통10점 중 7점

유형
기하, 이분 탐색, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

평면 위에 nn개의 점으로 이루어진 집합 AA가 주어진다. 직선 pp와 집합 AA 사이의 거리는 집합 AA의 각 점에서 직선 pp까지의 거리 중 가장 큰 값으로 정의한다.

고정된 점 PP를 지나는 모든 직선 중에서 집합 AA까지의 거리가 가능한 한 작아지는 직선을 고르고, 그 최소 거리를 구한다.

다음을 수행하는 프로그램을 작성하라.

  • 표준 입력에서 집합 AA와 점 PP의 위치를 읽는다,
  • PP를 지나는 직선이 집합 AA에 대해 가질 수 있는 최소 거리를 계산한다,
  • 그 값을 표준 출력에 쓴다.

입력

첫째 줄에 정수 nn (1≤n≤1000001 \le n \le 100000)이 주어진다.

둘째 줄에 점 PP의 좌표를 나타내는 두 정수가 주어진다.

이어지는 nn개의 줄에는 각각 집합 AA에 속한 한 점의 좌표를 나타내는 두 정수가 주어진다.

모든 좌표는 절댓값이 10610^6 이하인 정수이다.

출력

구하는 거리를 실수 하나로 출력한다. 소수점 아래 정확히 세 자리까지 나타내며, 내림(버림)하여 출력한다.

테스트는 오차가 10−610^{-6} 미만이면 이 내림 이후에도 정답이 나오도록 구성되어 있으므로, 소수점 아래 여섯 자리 정도의 정확도로 계산하면 충분하다.

예제2

  1. 예제 1

    입력
    8
    3 3
    3 1
    9 1
    7 4
    10 4
    4 5
    1 6
    5 9 
    8 8
    
    예상 출력
    4.472
    
  2. 예제 2

    입력
    3
    -8 -4
    8 -4
    -3 2
    -5 -3
    
    예상 출력
    4.395