Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: AQT
The problem is asking to find all the vertices to a non-degenerate convex polygon. We can try to find all the vertices by asking the judge a point
in which we get any vertex of the polygon that is closest to
.
For the first subtask all the range of points that could be on the polygon is small (
possible candidates). A sufficient algorithm for the first subtask is to query all points in the range and maintain a counter of all the times the queried point is equal to the point that has been returned.
For the other subtask, we note that a convex polygon must have two points
and
such that
. This means that the smallest
-coordinate is not the same as the largest
-coordinate. We can get those two points by querying points
and
for the vertex with the smallest and largest
-coordinate of the polygon.
Now consider, this method of constructing a polygon, knowing that we have at least
vertices
and
. We will now check if
and
are adjacent. For
and
to be adjacent, then all the vertices must strictly lie on one side of the line
and
. So, if there exist a point on the other side of the line, then
and
are not adjacent. We can try to find this point by using the following method.
- Let
be the midpoint of the line segment
and
.
- Draw a ray
that is perpendicular to the line segment
and
from
and extends towards the plane where a new point might potentially exist (the half-plane that does not contain the rest of the known points of the convex polygon).
- Let
be some point on the ray where either the absolute value of its
or
value is large and query that point.
Note that point that is being returned as
. If
is equal to either
or
, then we have not found any point between
and
. Otherwise,
and
are not adjacent as
is between, so we will repeat this process for the pairs
and
and
and
.
Since every edge and every vertex of the polygon will use up a
query, then we need to use
queries to find all the points.
A few tips when implementing. We can work with integer coordinates all the time by mapping all
. This way the midpoints will all have integer coordinates. Also, by repeating the process, we can think of it as divide-and-conquer on a polygon, so we can write it recursively or iteratively.
Comments