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:
Integer A
B : An integer array containing X-coordinates of the places
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:
Places can be overlapping (Two places can have same (X,Y) co-ordinates)
Overlapping places must not be considered as same places.
In case the line joining the places is vertical, slope is -INF.
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:
Output fraction should not be further reducible [e.g. Reduce (6,4) to (3,2) before returning the answer]
In case the answer is negative infinity, return (-1,0)
In case the answer is zero, return (0,1)
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.
Instead of copying the problem Statement, copy the problem link and paste here. Otherwise how will the community know it's not from an ongoing Contest.
Lmao. If no one wants to answer your post, what makes you think that bumping will help? It is just going to annoy people into giving you downvotes.
You can binary search it. To count how many pairs are before some ratio $$$\frac{a}{b}$$$, sort points in increasing order by both $$$x$$$ and $$$ax - by$$$. Keep a segment tree for changing value at position and prefix sum. Initialize the segment tree to the number of different values of $$$ax - by$$$, and initialize the $$$j$$$'th position to the number of points that have $$$ax - by$$$ equal to the $$$j$$$'th value.
Loop points by x-coordinate. If the current point is the $$$j$$$'th value in the array sorted by $$$ax - by$$$, decrement the value at the $$$j$$$'th position in the segment tree, then add the prefix sum up to $$$j$$$ to your answer. This counts the number of points s.t. the angle to them from the current point is at least $$$\frac{a}{b}$$$.
Once you have an accurate enough estimate for the angle (rational number with divisor larger than it can be for any of the actual ratios), do the same again, but also check for every point the previous active one in the segment tree, and take the ratio to that point as the offer, then return the minimum of the offers.
Time complexity is $$$O(n log^{2} n)$$$ since you binary search and do $$$n log n$$$ work inside it. This doesn't use the fact that $$$A \leq 70$$$ so there might be better ways to do this.
Note that some specifics could be wrong, geometry problems often have a ridiculous amount of corner cases and it's hard to know without coding the solution whether it works for sure.
Thanks, i will implement your solution. i understood the approach.
Another way of solving this problem is using point-line duality. In particular, mapping (a, b) -> y = ax — b turns lines connecting two points into points at the intersection of two lines, and vice versa. This means that your problem becomes: given an envelope of lines, find the intersection between a pair of lines that has the k-th smallest x coordinate.
To solve this new problem, we can once again binary search on the answer, but now our task becomes to find the number of pairwise intersections between N lines that occur before some given x coordinate. This can be reduced to inversion counting, so the total time complexity is O(N log^2 N).