만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

험지를 가로지르는 다리

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

요약
A와 B 사이의 산맥 선분에서 길이가 L을 넘지 않는 수평 다리의 두 끝점을 찾습니다. 다리 아래로 지형이 솟아 있으면 안 됩니다.
난이도

보통10점 중 7점

유형
기하, 투 포인터, 슬라이딩 윈도우
정답자
아직 제출이 없습니다

문제

우랄 산맥의 단면은 꺾은선 (x1,y1),(x2,y2),…,(xN,yN)(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)으로 주어지며, x1<x2<⋯<xNx_1 < x_2 < \dots < x_N을 만족합니다. 시작점과 끝점은 해수면 높이에 있으므로 y1=yN=0y_1 = y_N = 0입니다.

단면 위에 서로 다른 두 점 AA, BB가 있습니다. 이 두 점 사이에 도로를 놓아야 합니다. 도로는 산비탈과 수평인 다리를 지납니다. 다리의 길이는 LL을 넘을 수 없습니다. 다리의 양 끝은 모두 산의 단면 위에 있습니다. 도로는 다리의 한쪽 끝으로 들어가 다른 쪽 끝으로 나옵니다. 터널은 건설하지 않으므로, 다리는 꺾은선보다 엄격히 아래에 있는 점을 포함할 수 없습니다.

가능한 다리 위치불가능한 다리 위치

입력

첫 줄에 두 정수 NN, LL이 주어집니다. 2≤N≤100 0002 \le N \le 100\,000은 꺾은선 꼭짓점의 개수이고, 1≤L≤1061 \le L \le 10^6은 다리의 최대 길이입니다. 둘째 줄에는 점 AA의 좌표, 셋째 줄에는 점 BB의 좌표가 주어집니다. 이어지는 NN개의 줄에는 꺾은선 꼭짓점 (x1,y1),(x2,y2),…,(xN,yN)(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)이 주어집니다.

모든 좌표의 절댓값은 10610^6 이하입니다. x1<x2<⋯<xNx_1 < x_2 < \dots < x_N, y1=yN=0y_1 = y_N = 0이 보장되며, 점 AA와 BB는 꺾은선 위에 있습니다. 두 점은 서로 다릅니다.

출력

다리 양 끝의 좌표를 첫 줄과 둘째 줄에 소수점 아래 5자리 이상의 정확도로 출력합니다. 답이 여러 개이면 그중 아무거나 출력해도 됩니다.

예제2

  1. 예제 1

    입력
    4 6
    13 0
    2 1
    1 0
    5 4
    11 -2
    13 0
    
    예상 출력
    13.00000 0.00000
    9.00000 0.00000
    
  2. 예제 2

    입력
    6 8
    3 -6
    11 -2
    0 0
    4 -8
    6 -4
    7 -4
    9 -6
    12 0
    
    예상 출력
    2.00000 -4.00000
    10.00000 -4.00000