## Editorial for CEOI '14 P2 - Fangorn

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

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