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

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

조깅

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

요약
x좌표가 증가하는 순서로 주어지는 각 휴식점에서 x좌표가 더 큰 별까지의 각도 중 가장 큰 값을 라디안으로 소수점 일곱째 자리까지 출력하고 보이는 별이 없으면 0을 출력합니다.
난이도

보통10점 중 7점

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

문제

2차원 세계에 사는 대영이는 xx축 위의 점 하나로 나타낼 수 있다. 대영이는 저녁마다 조깅을 하는데, xx좌표가 커지는 방향으로만 달린다. 이 세계는 저녁만 되어도 하늘에 별이 총총히 뜬다. 달리다 힘들어지면 대영이는 잠시 멈춰 서서 하늘의 별을 바라본다.

별도 2차원 평면 위의 점이다. 대영이는 자기 xx좌표보다 xx좌표가 큰 별만 바라보고, 그중에서 가장 높이 있는 별이 무엇인지 알고 싶다. 높이 있다는 말은 그 별을 보려고 고개를 들어야 하는 정도, 즉 각도가 가장 큰 별이라는 뜻이다.

대영이가 점 (p,0)(p, 0)에서 쉬고 별이 점 (x,y)(x, y)에 있으면, 그 별을 보는 각도는 xx축의 양의 방향과 별을 향하는 반직선이 이루는 각 θ=arctan⁡yx−p\theta = \arctan \frac{y}{x - p}이다. 대영이가 쉴 때마다 그 순간 보이는 별의 각도 중 최댓값을 구하자.

조깅하는 대영이와 별이 이루는 각도

입력

첫째 줄에 별의 개수 NN과 대영이가 쉬는 횟수 MM이 공백을 사이에 두고 주어진다. (1≤N≤1051 \le N \le 10^5, 1≤M≤1051 \le M \le 10^5)

다음 NN개 줄에는 별 하나의 좌표를 나타내는 두 정수 xx, yy가 공백을 사이에 두고 주어진다. (∣x∣≤108|x| \le 10^8, 1≤y≤1081 \le y \le 10^8)

다음 MM개 줄에는 대영이가 쉬는 지점의 xx좌표가 한 줄에 하나씩 주어진다. 이 좌표는 증가하는 순서로 주어지며 절댓값이 10810^8 이하이다.

xx좌표가 같은 별이 여러 개 있을 수 있다.

출력

대영이가 쉴 때마다 보이는 별의 각도 중 최댓값을 라디안 단위로 소수점 아래 일곱째 자리까지 반올림해 한 줄에 하나씩 출력한다. 보이는 별이 하나도 없으면 0.0000000을 출력한다.

채점은 출력한 문자열을 그대로 비교한다. 모든 테스트에서 정답은 반올림 경계에서 충분히 떨어져 있어, 배정밀도 실수 연산으로 계산해도 같은 문자열이 나온다.

예제3

  1. 예제 1

    입력
    2 3
    4 4
    6 6
    -1
    1
    4
    
    예상 출력
    0.7086263
    0.9272952
    1.2490458
    
  2. 예제 2

    입력
    1 1
    5 5
    0
    
    예상 출력
    0.7853982
    
  3. 예제 3

    입력
    3 4
    -5 3
    0 7
    5 2
    -6
    -5
    0
    5
    
    예상 출력
    1.2490458
    0.9505468
    0.3805064
    0.0000000