Tangent ranges for all point pairs in a box
Taking the double plane idea proposed by Evgeny Kluev and my comment on finding the left intersection point, I will try to give an equivalent direct solution without any double space.
The solution is simple: sort your points by (x, y) lexicographically. Now draw a line through every two adjacent points in sorted order. It can be shown that the minimum angle is reached by one of these lines. To get the maximum angle, you need to sort by (x, -y) lexicographically and also check for adjacent pairs of points only.
Let the idea of the minimum angle be proved. Consider two points A and B that give the smallest possible angle. Among such points, we can choose a pair with the minimum difference in coordinates x.
-
Let's assume they have the same y. If there is no other point between them, they are adjacent. If there are any points between them, then obviously at least one of them is adjacent to A in our order, and they all give the same angle.
-
Suppose there is a point P with an x-coordinate between A and B, that is, Ax <Px <Bx. If P lies on AB, then AP has the same angle, but a smaller difference in x coordinates, hence a contradiction. When P is not on AB, then AP or PB will give you less angle, which also gives a contradiction.
-
We now have points A and B lying on two adjacent vertical lines. There are no other points between these lines. If A and B are the only points on their vertical lines, then AB is clearly adjacent in sorted order and QED. If there are many points on these lines, then obviously the minimum angle is achieved by taking the highest point on the left vertical line (which should be A) and the lowest point on the right vertical line (which should be B). Since we are sorting points equal to x by y, these two points are also adjacent.
source to share
Detach the dots (or use a hash map) to see if there are horizontal lines.
Then we will solve this problem on a double plane. Here you only need to find the left-most and right-most intersection points. Use binary search to find a pair of horizontal coordinates so that all intersection points are between them. (You can quickly find approximate results by simply continuing binary searches from these coordinates).
Then we sort the lines by their tangents on the double plane. And for pairs of adjacent lines, in this sorted order, find the intersections that are closest to those horizontal coordinates. This does not guarantee good complexity in the worst case (when some lines on the primary plane are almost horizontal). But in most cases the time complexity was determined by sorting: O (N log N) + O (binary_search_complexity).
source to share