만드는 중입니다

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

위잉위잉

면접 대비

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

요약
혁이 제자리에서 반시계 방향으로 돌 때 앞에 오는 사람들을 만나는 순서대로 좌표를 출력합니다. 같은 방향이면 가까운 사람부터 출력합니다.
난이도

보통10점 중 5점

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

문제

비잉비잉 돌아가는\n>\n> 세상도 나를 비웃듯이 계속 꿈틀대죠\n\n혁이는 백화점 한가운데서 NN명의 사람들에게 둘러싸여 있다. ii번째 사람의 위치는 평면 좌표 (Xi,Yi)(X_i, Y_i)이고, 혁이와 같은 위치에 있는 사람은 없다. 혁이는 사람들의 시간을 멈춘 뒤 제자리에서 반시계 방향으로 돌면서, 매 순간 정면에 놓인 사람들의 위치를 순서대로 기록한다. 정면에 사람이 여럿이면 혁이와 가까운 사람부터 기록한다.

입력

첫째 줄에 혁이를 제외한 사람의 수 NN이 주어진다. (1≤N≤300 0001 \le N \le 300\,000)

다음 NN개 줄에 혁이를 제외한 각 사람의 위치 XiX_i와 YiY_i가 공백으로 구분되어 주어진다. (−109≤Xi,Yi≤109-10^9 \le X_i, Y_i \le 10^9)

그다음 줄에 혁이의 위치 XHX_H와 YHY_H가 공백으로 구분되어 주어진다. 혁이는 (XH,YH)(X_H, Y_H)에 있다. (−109≤XH,YH≤109-10^9 \le X_H, Y_H \le 10^9)

출력

첫째 줄부터 NN개 줄에 걸쳐 혁이가 기록한 위치 XiX_i와 YiY_i를 공백으로 구분하여 한 줄에 하나씩 출력한다.

가능한 답이 여러 가지이면 아무거나 출력한다.

예제1

  1. 예제 1

    입력
    8
    5 -3
    10 1
    -1 2
    1 7
    2 1
    2 5
    5 4
    6 -1
    3 2
    
    예상 출력
    -1 2
    2 1
    5 -3
    6 -1
    10 1
    5 4
    2 5
    1 7