CodinGame-Solutions/Puzzles/Easy/Dead men's shot/Java.java at master · pathosDev/CodinGame-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/****************************************/
/*                                      */
/* CodinGame.com Solutions by pathosDev */
/*                                      */
/* Puzzle: Dead men's shot              */
/* Difficulty: Easy                     */
/* Date solved: 19.11.2018              */
/*                                      */
/****************************************/

import java.awt.Point;
import java.util.Scanner;

public class Solution
{
    public static void main(String[] args)
    {
        //Read inputs.
        Scanner scanner = new Scanner(System.in);

        int N = Integer.parseInt(scanner.nextLine());

        Point[] corners = new Point[N];

        for (int i = 0; i < N; i++)
        {
            String[] cornerXY = scanner.nextLine().split(" ");
            int cornerX = Integer.parseInt(cornerXY[0]);
            int cornerY = Integer.parseInt(cornerXY[1]);

            corners[i] = new Point(cornerX, cornerY);
        }

        int M = Integer.parseInt(scanner.nextLine());

        for (int i = 0; i < M; i++)
        {
            String[] shotXY = scanner.nextLine().split(" ");
            int shotX = Integer.parseInt(shotXY[0]);
            int shotY = Integer.parseInt(shotXY[1]);

            //Check if current shot lays in the polygon or not.
            if (pointInPolygon(corners, shotX, shotY))
            {
                System.out.println("hit");
            }
            else
            {
                System.out.println("miss");
            }
        }
    }

    //Checks if a point lays inside a polygon or not.
    private static boolean pointInPolygon(Point[] polygon, double px, double py)
    {
        boolean collision = false;

        for (int current = 0; current < polygon.length; current++)
        {
            Point vc = polygon[current];
            Point vn = polygon[(current + 1) % polygon.length];

            boolean btv = (vc.y > py) != (vn.y > py); //Check if between vc.y and vn.y.
            boolean jct = px < (vn.x - vc.x) * (py - vc.y) / (vn.y - vc.y) + vc.x; //Jordan Curve Theorem.

            if (btv && jct)
            {
                //Swap collision state.
                collision = !collision;
            }
        }

        return collision;
    }
}