Time limit
2s
Memory limit
128 MB
You are given N distinct points on a plane. All x-coordinates are distinct, and all y-coordinates are distinct.
For two points (x1,y1) and (x2,y2), the absolute value of the slope of the line passing through them is
x2−x1y2−y1
Write a program that finds the two point numbers whose absolute slope is as large as possible.
The first line contains the number of points N. (2≤N≤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.
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.