### PROBLEM LINK:

**Author:** Pavel Sheftlevitch

**Tester:** Antoniuk Vasyl and Misha Chorniy

**Editorialist:** Praveen Dhinwa

### 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**

Assume that we want to solve the same problem for 2D version. So, sphere will be replaced by a circle.

Let us say that we want to check number of observable astroids from a point p on the circle.

Tangent at point p divides the space into two half planes, one of them is visible by p and other is not.

An astroid will be said to be visible if distance between it and the tangent plane at p is at least 10^{-3}.

So, now we can count the number of astroids visible from a point on the circle (i.e. number of points in the visible halfplane of tanget at point p).

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**

Similar to above, tangent at a point on the plane will divide the space into two halfs : visible and non-visible.

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.