# Codingame Solution: Dead men's shot

Original Problem

Captain Jack Sparrow and his pirate friends have been drinking one night. After plenty of rum, they got into an argument about who is the best shot. Captain Jack takes up some paint and paints a target on a nearby wall. The pirates take out their guns and start shooting.

Your task is to help the drunk pirates find out which shots hit the target.

Captain Jack Sparrow drew the target by drawing N lines. The lines form a convex shape defined by N corners. A convex shape has all internal angles less than 180 degrees. For example, all internal angles in a square are 90 degrees.

A shot within the convex shape or on one of the lines is considered a hit.
Input
Line 1: An integer N for the number of corners.
Next N lines: Two space-separated integers x and y for the coordinates of a corner. The corners are listed in a counterclockwise manner. The target is formed by connecting the corners together with lines and connecting the last corner with the first one.
Line N+1: An integer M for the number of shots.
Next M lines: Two space-separated integers x and y for the coordinates of each shot.
Output
M lines with either "hit" or "miss" depending on whether the shot hit the target or not.
Constraints
3 ≤ N ≤ 10
1 ≤ M ≤ 10
-10000 < x,y < 10000

## Solution

The classical solution to check if a point falls into a polygon is putting an infinite horizontal line to the point and count the number of intersections with edges of the polygon. If the number is odd, the point must be within the polygon.

Here we will do it differently since we know the polygon is convex. This means that when taking a random starting point and follow the path all around the polygon, we have made a perfect circular tour. It is obvious that when doing that tour, the point will always be on one side. Testing if this side changes even once therefore solves the test of a point being in a convex polygon. To check if the side changes, we calculate the 2D cross-product of the vector from a starting point $$A$$ to a successive point $$B$$ and the vector from $$A$$ to the target point $$P$$. The 2D cross-product is defined as $$\mathbf{u}\times\mathbf{v}=det(\mathbf{u}\mathbf{v})$$ and the sign of the resulting scalar desides the direction. As such the problem can be solved with the following implementation:

function inPoly(Px, Py, poly) {

let flag = 0;

for (let i = 0; i < poly.length; i++) {

const j = (i + 1) % poly.length;

// Current point A
const Ax = poly[i][0];
const Ay = poly[i][1];

// Successive point B
const Bx = poly[j][0];
const By = poly[j][1];

// 2D Cross product
const d = (Px - Ax) * (By - Ay) - (Py - Ay) * (Bx - Ax);

flag|= 1 << (d <= 0);

if (flag === 3) {
return false;
}
}
return true;
}

const E = [];
for (let i = 0; i < N; i++) {
}

for (let i = 0; i < M; i++) {
const [x, y] = readline().split(' ').map(Number);
print(inPoly(x, y, E) ? "hit" : "miss");
}


« Back to problem overview