위잉위잉

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

요약
중심을 기준으로 N개 점을 각도순으로 정렬하고, 같은 각도에서는 거리가 가까운 점을 먼저 출력하는 문제입니다.
난이도

보통10점 중 6점

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

문제

비잉비잉 돌아가는

세상도 나를 비웃듯이 계속 꿈틀대죠

혁이는 백화점 한가운데서 NN명의 인파에 둘러싸여 있다. ii번째 사람의 위치는 평면좌표 (X_i,Y_i)(X\_i, Y\_i)로 표현되고, 혁이와 같은 위치에 있는 사람은 없다. 혁이는 사람들의 시간을 멈추고, 반시계 방향으로 제자리에서 돌면서 매 순간 정면에 놓인 사람들의 위치를 순서대로 기록하려 한다. 정면에 사람이 여럿 있을 경우, 혁이에게 가까운 사람부터 그 위치를 기록한다.

사람들과 혁이의 위치가 주어질 때, 혁이가 기록한 위치들을 순서대로 출력하는 프로그램을 작성하자.

입력

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

다음 NN개 줄에 혁이를 제외한 각 사람의 위치를 나타내는 정수 X_iX\_i와 Y_iY\_i가 공백으로 구분되어 주어진다. (−109≤X_i,Y_i≤109-10^9 \le X\_i, Y\_i \le 10^9)

그다음 줄에 혁이의 위치를 나타내는 정수 X_HX\_H, Y_HY\_H가 공백으로 구분되어 주어진다. 혁이는 (X_H,Y_H)(X\_H, Y\_H)에 있다. (−109≤X_H,Y_H≤109-10^9 \le X\_H, Y\_H \le 10^9)

출력

첫째 줄부터 NN개 줄에 혁이가 기록한 위치를 나타내는 X_iX\_i와 Y_iY\_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