Let's denote the position of the first ship with ~P~. The first part of the task is to find the set of points ~S~ that are visible from point ~P~ – the receiver of the Mayday message. The second part of the problem is to find the set of points ~S'~ that are visible from at least one point from set ~S~ – the receivers of the Relay message. In the rest of this text, the expression to the left or right of line ~P~ is often used and means that, if the observer is at point ~P~ and is looking towards point ~L~, something is to the right or to the left of that line. This expression directly corresponds to the geometric primitive CCW that is most often implemented using the vector product. The polygon edges are given counterclockwise, so we will use the expressions before or after point ~T~, and will be denoted respectively with ~B_t~ and ~A_t~.

We determine the points that are visible from ~P~ using the left and right tangent, ~PL~ and ~PR~. All points to the left of ~PL~ and to the right of ~PR~ are directly visible. Additionally, points inside the triangle ~PRL~ are directly visible. The right tangent from point ~P~ is determined in a way that we find the edge ~R~ for which it holds that point ~P~ is to the right of side ~B_r R~ and to the left of side ~R A_r~. The left tangent is determined in a similar way.

We find points from set ~S'~ so that we first find the points that receive the Relay signal from points to the left of ~PL~, then in the same way, determine those that receive the Relay signal from points to the right of ~PR~. We will only describe the process for the left tangent. Let ~K~ denote the set of points to the left of ~PL~. In the picture, these points are ~P_3~, ~P_7~, ~P_{10}~ and ~P_{11}~, and the red lines are their left tangents, in the rest of the text just tangents.

Let's observe which area is covered by point ~T~ from set ~K~, without it being covered by the starting point ~P~. Let ~TT'~ be the tangent that touches the polygon in point ~T'~ and let ~C~ be the intersection of tangents ~TT'~ and ~PL~. This area consists of all points to the left of ~TT'~ and to the right of ~PL~, and of all points inside the triangle ~CLT'~.

Notice that the point which has the tangent that forms a smaller angle with the line ~PL~ has an area that is a subset of the area of the point that has the tangent that forms a larger angle. This means that we only need to find the point that has the tangent that forms the largest angle and count the points that are visible from it. The only other problem is how to calculate the tangent to the polygon from every point. If we denote edge ~L~ with index ~1~ and denote other edges clockwise with ascending indices, then the edge in which the tangent from the required point touches the polygon will have the largest index (among points from set ~K~). This is why we will maintain the largest index thus far and increment it with every new point until it becomes the edge in which the tangent from the current point touches the polygon. When we test whether we need to increment the index from point ~T~, we only need to check if the next edge in the polygon is to the left of the length that connects ~T~ to the current edge. If it is, then we increment the index.

Regarding implementation, we need to pay attention to the collinearity of points and make sure that the edge points between areas are not counted multiple times. The total complexity of the algorithm is ~\mathcal O(N)~.

For the curious reader: Solve the version of the task where in each step we give two points ~a~ and ~b~ and ask whether ~b~ will receive one of the signals if ~a~ transmits the Mayday signal. You are given ~100\,000~ queries, all other limitations stay the same.