Editorial for CEOI '14 P2 - Fangorn
Submitting an official solution before solving the problem yourself is a bannable offence.
Definition 1. A portal is a straight line connecting two trees. A point is called allowed if you can see all trees from it. A path is allowed (or valid), if all of its points are allowed. If a point is not allowed, we call it forbidden, and likewise for paths.
The main point of our solution is that for any camp, we only need to check two paths. The proof will consist of several steps.
Remark 2. If is reachable from
(meaning there is a valid path connecting them), then this is still possible if we restrict ourselves to piecewise linear paths that only bend on portals.
Proof. First note that the set of forbidden points is given as follows: for any pair of trees, we have a "forbidden ray" going out of
with direction
(these are precisely the points where you can't see
because of
). Thus if we remove forbidden points and all the portals, we get the plane with some lines removed, which splits into convex regions. Thus any two points on portals bounding the same region can be connected by a straight line of allowed points. □
The most important result is the following:
Lemma 3. If is reachable from
and at least one of them lies on a portal, then the segment
is valid.
Proof. W.l.o.g. assume that lies on a portal and let
be a valid piecewise linear path connecting
and
which has
bend points. We can restrict ourselves to the case
: for
, there is nothing to show and the general case follows easily by induction.

Let be the bend point and consider the triangle
formed by
,
, and
. Assume that
would be forbidden, i.e. there is a forbidden ray intersecting
. Let
be the respective line. Since
would intersect one of the other two sides, there must be a tree
inside
. Now take one tree
of the portal which is not on the same side of
as
. Then
intersects
and thus another side of
. At this intersection point,
is hidden by
and so it is forbidden, which contradicts the choice of
. □
Fix a portal. If we remove all the forbidden points from this portal, it splits into a set of segments. Obviously, for any
, either all points are reachable or none. Applying the previous lemma, we see that a segment is reachable if and only if the midpoint is reachable via a direct line.
Hence we can give an algorithm, which scores 20 points, as follows: for any of the
portals calculate all intersections with the
forbidden rays. This gives up to
segments. Then for a fixed camp and any segment, check if we can reach the midpoint from both the camp and Gimli via a direct line, which needs
intersection checks per midpoint. Finally, check the direct line from Gimli to the camp itself.
For any polygon , we denote by
its border. The following result allows us to optimise the above algorithm:
Remark 4. Let denote the forest (as in the task statement) and let
be the convex hull of the trees. As above, let
and
be arbitrary points in
. If
lies on
and is reachable from
, then it is already reachable either via a direct line or via a piecewise linear path having its only bend point on
.
Proof. Let be an allowed path from
to
that bends only on portals. If
intersects
this follows as above. Otherwise, since
is not contained in the interior of
, the whole path must lie outside
and thus cannot intersect any portal. Hence, by construction,
is a segment. □
In , we can calculate all intersections between
and forbidden rays. By convexity, any ray can intersect
in at most
point, hence there are only
segments to consider. Thus the obvious modification of the above algorithm has runtime
, which gets another 20 points (10 points from the convex subtask).
If all trees lie on , then all forbidden points (except the trees) are outside
and hence you only need to look at midpoints of portals on
. This gives an
algorithm which scores 20 points, or when combined with the above solution, 50 points.
For 80 points, you need the following observation:
Definition 5. Fix a tree . The forbidden rays beginning at
split the plane into different regions, exactly one of which contains Gimli's original position. The two rays bounding this region and their points are called strictly forbidden.
Remark 6. A path beginning at Gimli's original position is allowed if and only if it contains no strictly forbidden points.
Proof. The "only if" part is trivial. Now let be a forbidden point, that is not strictly forbidden, and
the respective tree. Then by definition,
must cross one of the forbidden rays beginning at
in order to reach
, i.e. it must contain a strictly forbidden point. □
The forbidden rays can be easily found in . From this, we can get an
solution by applying the above procedure only to the strictly forbidden rays: all the midpoints omitted are anyhow not reachable from Gimli.
For full score, you can use the following final result:
Remark 7. Let and
be points on (possibly distinct) portals, that are both reachable from Gimli, and let
be an arbitrary point. Then the segment
is allowed if and only if
is valid.
Proof. Note that you can get from to
and vice versa (simply by composing the paths to Gimli's original position). Thus
is reachable from
iff it is reachable from
. So the claim follows from Lemma 3. □
So we can solve the problem in as follows: calculate the forbidden rays as above and then in
the reachable segments on
. Then for any camp
, check both the direct line from Gimli's original position to
and, if it exists, the direct line from an arbitrary reachable midpoint to
.
Some further notes
The proof of our main lemma only requires that there are trees on either side of . As you can see from the practice task "surveyor", this holds if either
or
is contained in the convex hull
. Thus, we do not need the restriction that all the camps are located on
: any point inside
is reachable via a direct line, and for Remark 4, we only require
to be outside
. Hence the above algorithm also works in general.
After preprocessing time, we only need to check for up to two points which camps are reachable via a direct line. This could be also done in
by sweeping over angles.
The following proposition offers an easier to implement solution.
Proposition 8. For any tree , removing the strictly forbidden points (including
) splits the plane into two parts, exactly one of which contains Gimli's original position. Call this region
. Then a camp
is reachable from Gimli if and only if it is contained in
for all trees
.
Proof. Obviously, every point reachable from Gimli's original position lies in the intersection of all . It remains to show that the intersection of all regions
is connected.
If the tree lies inside the convex hull
of the forest, the region
is the intersection of two half-planes (in particular convex). On the other hand, this need not be the case if
is a corner of the convex hull. But if
is non-convex, it is easy to see that
at least contains all other trees (cf. Figure 1).
We are now going to show that for any subset of the set of non-convex regions and any set of half-planes through trees, the intersection of these non-convex regions and half-planes is connected. This is obviously sufficient to prove the claim, as it implies that the intersection of all regions
is connected. We are going to use induction on the number of non-convex regions we consider. The intersection of half-planes is convex and thus connected, so we may assume that there is at least one such non-convex region
. Let
be the intersection of the half-planes and the other non-convex regions. By drawing a picture, you can easily see that
lies completely within a half-plane through the tree
contained in
or
is contained in (or on the border of)
(since
lies in all non-convex regions
and lines through trees cannot divide
from both
and
, cf. Figure 2).
In the first case, simply apply the induction hypothesis (replacing the non-convex region by the half-plane through
). In the second case, split
into two convex regions
and
using a line through
. Both regions are the intersection of two half-planes through
, so by induction, the sets
and
are both connected. Furthermore,
is contained in (or on the border of)
and
. But that means that the union
is connected (two points
and
are connected via a point close to
, cf. Figure 3). □
Note that this relies heavily on the structure of the 's and is false for arbitrary sets. For example, you can take the sets
and
obtained by removing from the unit circle the points
and
, respectively. Then both
and
contain paths from
to
, but their intersection doesn't.
Comments