시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 75 13 9 18.367%

문제

평면상에 N개의 서로 다른 점들이 주어져 있을 때, 그 중 임의의 두 점을 지나는 직선의 기울기의 절대값이 가장 큰 두 점을 찾고 싶다. 두 점의 좌표가 (x1, y1), (x2, y2) 라고 할 때, 기울기의 절대값은 다음과 같은 수식으로 표현된다.

| (y2-y1) / (x2-x1) |


  모든 점의 x좌표는 다르다고 하자. 또한, 모든 점의 y좌표 역시 다르다고 하자.

점들의 좌표가 주어지면 임의의 두 점을 지나는 직선의 기울기의 절대값이 가장 큰 두 점을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(1≤N≤50,000)이 주어진다. 이어서 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표는 절대값이 30,000을 넘지 않는 정수이다. 모든 점은 입력되는 순서대로 1번부터 N번까지 번호가 매겨진다.

출력

기울기의 절대값이 가장 큰 두 점의 번호 A와 B를 빈 칸을 사이에 두고 출력한다. (A<B) 그러한 두 점의 쌍이 둘 이상인 경우 A가 가장 작은 것을 출력하고, 만일 A가 가장 작은 답도 여러 가지가 있으면 B가 가장 작은 것을 출력한다.

예제 입력

5
1 1
6 5
4 7
3 9
2 10

예제 출력

1 5

힌트

출처

  • 문제를 번역한 사람: author5