How to find the kth maximum slope in this problem.

Правка en1, от atlasworld, 2019-07-06 12:47:17

Maroof is visiting a new city. Being a Mathematician, he does not like to visit different places but visit places differently. The city has N places to visit. We are given the (X,Y) co-ordinates of the places to visit. Maroof wants to start from a random place i and want to go to a random place j. But he involved a little maths in his procedure. Following are his demands:

He will give a number A. Now, the place i and place j should be such that the line connecting these two points must have the Ath maximum slope (There are total N*(N-1)/2 possible slopes among all the unordered places pairs).

Input arguments to your function:

  1. Integer A
  2. B : An integer array containing X-coordinates of the places
  3. C : An integer array containing Y-coordinates of the places

Note that the length of B (= N) will be equal to the length of C and the ith point is represented by (B[i], C[i]).

Output: An array having exactly 2 elements : numerator and denominator of the slope (fraction should not be further reducible).

Additional instructions:

  1. Places can be overlapping (Two places can have same (X,Y) co-ordinates)
  2. Overlapping places must not be considered as same places.
  3. In case the line joining the places is vertical, slope is -INF.
  4. Two overlapping places have slope -INF.

Constraints:

1 <= A <= 70 1 <= N <= 100,000 -10^9 <= B[i], C[i] <= 10^9 (Also X and Y coordinates can only be Integers)

Example:

Input: A = 2 B = [1, 2, 3, 1, 2] //X coordinates of the places C = [2, 4, 6, 2, 3] //Y coordinates of the places

Output: ans = [2,1].

Sorted Points = [(1,2), (1,2), (2,4),(2,3),(3,6)] SortedSlopes: [3, 2, 2, 2, 2, 2, 1 , 1, -INF, -INF]

Output instructions:

  1. Output fraction should not be further reducible [e.g. Reduce (6,4) to (3,2) before returning the answer]
  2. In case the answer is negative infinity, return (-1,0)
  3. In case the answer is zero, return (0,1)
  4. In case the answer is negative, numerator must be negative. [e.g.: (-3,2) not (3,-2) ]

Any idea how to solve it in linear or linear log time.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский atlasworld 2019-07-07 12:33:42 30
en2 Английский atlasworld 2019-07-06 12:48:02 30
en1 Английский atlasworld 2019-07-06 12:47:17 2157 Initial revision (published)