Yo!
I lied. I actually have 2 problems:
Given n vertical line segments i.e. they are parallel to the y axis, find if there exists a straight line of any slope which passes through all the given line segments.
Given n lines such that none are parallel and there are nC2 intersection points, find the number of intersection points to the right of y axis and do this in most optimized time complexity.
I welcome all solutions :)
Thanks!
For problem two: calculate the y axis intercept of each line. Create an array of lines sorted by y intercept. Next make a set of lines ordered by their slope. Walk through the array of lines in order and find where they exist in the set. All the lines they intersect with start above them and therefore must have a smaller slope. Count them. Remove the current line from the set before continuing, to avoid doublecounting.
For problem 1: Consider each pair of line segments. We can calculate the minimum and maximum allowable slope between them by drawing though the lower and upper, or upper and lower points respectively. The intersection of all the allowable slopes between each pair is the valid slopes for the whole set. Given any valid slope, we can use a binary search on one segment to determine some valid line with such a slope.
We can improve the above algorithm by considering that we can always modify a solution line to rest against two endpoints.
Make convex hulls of the top endpoints and the bottom endpoints. Check if they intersect. If they intersect there is no solution. If they do not intersect there is some solution, and it is one of the convex hulls line segments extended. We can find it quickly by walking around the lower Hull and maintaining the points the current line intersects with the upper hull. When moving line to line, it must sweep over points next to the given points of impact on the upper hull, so we can consider only the points next to the old line to walk to the new state. On a full revolution, we will sweep over each point only twice, so out complexity is linear. Once our points of intersection meet, we no longer have an intersection and have found our solution.
If we do not find a solution from the bottom hull, we can repeat the process for the top.
Problem 1 is similar to this problem. Solution
Problem 1 can be attacked with duality. Suppose you have a line segment (x1,y1) to (x1,y2). Then the set of pairs (m,b) defining lines that pass through the segment are exactly the pairs satisfying:
$$$y1 <= mx1 + b <= y2$$$
which can be rewritten as:
$$$y1 - mx1 <= b <= y2 - mx1$$$
Now if we consider m and b as our variables, this defines 2 half planes that our pair (m,b) must live in. Take this over all the segments and the problem reduces to finding if intersection of a set of half planes is non-empty which is well known (e.g: https://mirror.codeforces.com/topic/62055/en1)
And actually the problems seem equivalent at least if you allow some of your vertical segments to be rays. But I think you can simulate rays by just taking large enough y coordinates.