cho.sh
Notes
Loading...

Two Points with the Greatest Slope

Time limit

2s

Memory limit

128 MB

Problem

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

For two points (x1,y1)(x_1, y_1)(x1​,y1​) and (x2,y2)(x_2, y_2)(x2​,y2​), the absolute value of the slope of the line passing through them is

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

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 NNN. (2≤N≤50,000)(2 \le N \le 50,000)(2≤N≤50,000)

Each of the next NNN 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 NNN in input order.

Output

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

If more than one pair satisfies the condition, print the pair with the smallest AAA. If there is still more than one such pair, print the one with the smallest BBB.