ASTRD - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

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.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

2

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 CodeChef: Practical coding for everyone

3

I did it in a simpler way. I just considered all planes tangent to planet and passing through 2 asteroids. It can be seen that we can move the plane which has minimum number of asteroids on its side to arrive at this state. So its just O(n^2) planes to consider. We can check how many asteroids are visible in linear time for each case.

2 Likes
4

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.

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.

1 Like
5

I did it in the same way :stuck_out_tongue:
But was getting WA for a long time, just because of the fact that multiple asteriods can be present at the same point.

1 Like
6

How you took that particular plane?
I did the same but had to use binary search type thing, thus making my Complexity reach O(n^3 logn)