use v6;

sub parse-line($str) {
    $str.split(/\s+/).map: { [ .split(',')>>.Rat ]; }
}

sub is-point-in-polygon($point, @poly) {
    # count intersections between a vertical line from
    # -Inf to $point and the lines in @poly.
    # iff the count is odd, the point is inside the polygon.

    my ($x, $y) = $point.flat;
    sub vertical-intersection(@p1, @p2) {
        my @x = (@p1[0], @p2[0]).sort;
        my @y = (@p1[1], @p2[1]).sort;

        if @x[0] >= $x || @x[1] < $x || @y[0] > $y {
            # the line ($p1 -> $p2) is completely right, left or above the
            # point, so it can't intersect with our virtual vertical line
            return 0;
        }
        if all(@x) == $x {
            # a vertical line below or overlapping the point
            return @y[1] >= $y ?? 1 !! 0;
        }
        return 1 if @y[1] < $y;

        my $slope = (@p2[1] - @p1[1]) / (@p2[0] - @p1[0]);
        my $y-axis-intercept = $slope * ($x - @p1[0]) + @p1[1];
        return ($y-axis-intercept < $y).Int;
    }

    my $intersections = 0;
    for @poly Z @poly.rotate -> $p1, $p2 {
        $intersections += vertical-intersection($p1, $p2);
    }
    return so $intersections % 2;
}

multi MAIN() {
    my @poly-points = parse-line(get);
    my $test-point  = parse-line(get).[0];
    if $test-point ~~ Array && @poly-points > 1 {
        say is-point-in-polygon($test-point, @poly-points) ?? 'yes' !! 'no';
    } else {
        say "invalid input";
    }
}

multi MAIN('test') {
    use Test;
    plan *;

    my @points =  parse-line('1.0,1.0 1.0,-1.0 -1.0,-1.0 -1.0,1.0');
    ok  is-point-in-polygon([0,  0], @points), 'masaks example';
    nok is-point-in-polygon([0,  2], @points), 'masaks example with (0, 2)';
    nok is-point-in-polygon([2,  0], @points), 'masaks example with (2, 0)';
    nok is-point-in-polygon([0, -2], @points), 'masaks example with (0, -2)';
    nok is-point-in-polygon([-2, 0], @points), 'masaks example with (-2, 0)';
    nok is-point-in-polygon([1, -2], @points), 'masaks example with (1, -2)';
    nok is-point-in-polygon([1,  2], @points), 'masaks example with (1,  2)';
    nok is-point-in-polygon([-2, 1], @points), 'masaks example with (-2, 1)';

    # triangle
    #   (0,2)  +------+ (1, 2)
    #          |     /
    #          |   /
    #          |  /
    #          |/
    #   (0, 0) +

    my @triangle = parse-line('0.0,0.0 0.0,2.0 1.0,2.0');
    ok  is-point-in-polygon([0.5, 1.1], @triangle), 'triangle (+)';
    nok is-point-in-polygon([0.5, 0.9], @triangle), 'triangle (-)';
    @triangle.=reverse;
    ok  is-point-in-polygon([0.5, 1.1], @triangle), 'triangle (+, rot)';
    nok is-point-in-polygon([0.5, 0.9], @triangle), 'triangle (-, rot)';

    # also try a triangle with a negative slope
    #   (1, 3)   +
    #            | \
    #            |  \
    #            |   \
    #            |    \
    #   (1, 1)   +-----+  (2, 1)
    @triangle = parse-line('1.0,1.0 1.0,3.0 2.0,1.0');
    nok is-point-in-polygon([1.5, 2.1], @triangle), 'triangle (+)';
    ok  is-point-in-polygon([1.5, 1.9], @triangle), 'triangle (-)';
    @triangle.=reverse;
    nok is-point-in-polygon([1.5, 2.1], @triangle), 'triangle (+)';
    ok  is-point-in-polygon([1.5, 1.9], @triangle), 'triangle (-)';

    # non-convex shapes
    #   (0,2)  +-------+ (2, 2)
    #          |     /
    #          |    /
    #          |   /
    #          |  /
    #   (0, 0) |  +  (0, 1)
    #          |  \
    #          |   \
    #          |    \
    #          |     \
    #  (0, -2) +------+  (2, -2)

    my @nc = parse-line('0.0,-2.0 0.0,2.0 2.0,2.0 0.0,1.0 2.0,-2.0');
    ok  is-point-in-polygon([1.5, -1.3], @nc),
                'lower half of non-convex polygon (+)';

    nok is-point-in-polygon([1.5, -0.8], @nc),
                'lower half of non-convex polygon (-)';
    nok is-point-in-polygon([1.5, 0.8], @nc),
                'lower half of non-convex polygon (+)';

    ok  is-point-in-polygon([1.5, -1.3], @nc),
                'lower half of non-convex polygon (-)';

    #     (0, 1) +
    #           / \
    #          /   \
    # (-1, 0) +     + (1, 0)
    #          \   /
    #           \ /
    #     (0, -1) +

    my @diamond = parse-line('-1,0 0,1 1,0 0,-1');
    ok  is-point-in-polygon([0, 0], @diamond),
            'diamond: test point above a polygon node';
    nok is-point-in-polygon([1, 1], @diamond),
            'diamond: upper right';
    nok  is-point-in-polygon([0, 2], @diamond),
            'diamond: above two polygon nodes';

    done_testing;
}