Two Points with the Greatest Slope

Time limit2sMemory limit128 MB

Summary

Given N points with distinct x and y coordinates, find the pair whose line has the largest absolute slope, breaking ties by smallest indices.

Level: Hard8 of 10
Topics: Divide and conquer, Geometry, Sorting, Math
Solved: No attempts yet

Problem

You are given $N$ distinct points on a plane. All x-coordinates are distinct, and all y-coordinates are distinct.

For two points $(x_1, y_1)$ and $(x_2, y_2)$ , the absolute value of the slope of the line passing through them is

$\left|\frac{y_2-y_1}{x_2-x_1}\right|$

Write a program that finds the two point numbers whose absolute slope is as large as possible.

Input

The first line contains the number of points $N$ . $(2 \le N \le 50,000)$

Each of the next $N$ lines contains the x-coordinate and y-coordinate of one point, separated by a space. Every coordinate is an integer with absolute value at most 30,000. The points are numbered from 1 to $N$ in input order.

Output

Print the numbers $A$ and $B$ of the two points with the greatest absolute slope, separated by a space. Print them so that $A < B$ .

If more than one pair satisfies the condition, print the pair with the smallest $A$ . If there is still more than one such pair, print the one with the smallest $B$ .

Examples1

Example 1
Input
```
5
1 1
6 5
4 7
3 9
2 10
```
Expected output
```
1 5
```