PROBLEM LINK:Author: Pavel Sheftlevitch DIFFICULTY:hard PREREQUISITES:3D geometry, intersection of two circles in 3D PROBLEM:Given a sphere of radius $R$ and center at $(0, 0, 0)$. You are given $n$ astroids lying outside the sphere. An asteroid can be observed from a point if it's at least $10^{3}$ above the horizon line at the place of the observation. You need to find out minimum possible number of asteroids you can observe from some point on the suface of the sphere. EXPLANATION:Let us solve 2D version first Now, for finding the minimum number of visible astroids, we need to search over all possible points on the surface (perimeter) of the circle. As number of points on the circle are not finite, so our search space is infinite. So, we need to make some observations in order to reduce our search space to a finite set of points on circle. Let us think in reverse, i.e. instead of asking what are the set of points on the circle visible by an astroid located at point p? We can draw two tangents from point p on the circle. The visibile part will be the arc subtended by this point whose endpoints are intersection of tangent and circle. For each pair of points, we check whether their arcs intersect with each other or not. We include the intersection points in our search space. Other than those, for each astroid, we include the endpoints of arcs also in the search space. So, total number of points in search space can be $O(n^2)$. Checking for each point in search space will take another $O(n)$ time making it an $O(n^3)$ algorithm. Extend it to 3D version Now the visible surface by an astroid on the surface of planet will be a circle. For finding search space, we can take each pair of these circles and include their intersection points in the search space. If a circle does not intersect with any other, we can choose any two points on the surface in the search space. We will need to make use of 3D geometry to find the intersection points of two circles in 3D. You can learn it from here. Finally, overall time complexity of the algorithm is $O(n^3)$ same as the 2D case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 11 Jan '16, 09:52

If two arcs,which are on a circle, intersect at a point then that point is the endpoint of an arc. The other way they can intersect is have an overlap. But in this case points of intersection are infinite. Please explain. answered 04 Feb '16, 09:54

Solved it in O(N^2) time per case. Main part of solution is same, as in editorial, but when found arcs intersecting with current circle, you can do sort of scanline on this circle. First we sort start and end points' angles (from PI to PI) of arcs. Starting from PI with initial counter set as number of arcs crossing PI point, we increase counter when at start point and decrease when we at end point. Here is my AC solution https://www.codechef.com/viewsolution/9134966 answered 11 Jan '16, 15:56
