기울기가 가장 큰 두 점

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

요약
x좌표와 y좌표가 모두 다른 N개의 점 중에서 절댓값 기울기가 가장 큰 두 점을 찾고, 동일하면 인덱스가 작은 쌍을 출력합니다.
난이도

어려움10점 중 8점

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

문제

평면 위에 서로 다른 점 N개가 주어진다. 모든 점의 x좌표는 서로 다르고, y좌표도 서로 다르다.

두 점의 좌표가 (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2)일 때, 두 점을 지나는 직선의 기울기 절댓값은 다음과 같다.

∣y2−y1x2−x1∣\left|\frac{y_2-y_1}{x_2-x_1}\right|

주어진 점들 중 이 값이 가장 큰 두 점의 번호를 구하는 프로그램을 작성하라.

입력

첫째 줄에 점의 개수 NN이 주어진다. (2≤N≤50,000)(2 \le N \le 50,000)

다음 NN개의 줄에는 각 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다. 좌표는 절댓값이 30,000을 넘지 않는 정수이다. 모든 점은 입력 순서대로 1번부터 NN번까지 번호가 매겨진다.

출력

기울기 절댓값이 가장 큰 두 점의 번호 AA와 BB를 공백으로 구분해 출력한다. 항상 A<BA < B가 되도록 출력한다.

조건을 만족하는 점 쌍이 여러 개라면 AA가 가장 작은 쌍을 출력한다. 그런 쌍도 여러 개라면 BB가 가장 작은 쌍을 출력한다.

예제1

  1. 예제 1

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