#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

{   package Point;
    use Moo;
    use Types::Standard qw( Int );

    has [qw[ x y ]] => (is => 'ro', isa => Int);
}

{   package Jarvis;

    sub _ccw {
        my ($p, $q, $r) = @_;
        return (
            ($q->y - $p->y) * ($r->x - $q->x)
            - ($q->x - $p->x) * ($r->y - $q->y)
        ) < 0
    }

    sub convexHull {
        my ($points) = @_;
        return if @$points < 3;

        my @next = (-1) x @$points;

        my $leftmost = 0;
        for my $i (1 .. @$points - 1) {
            $leftmost = $i if $points->[$i]->x < $points->[$leftmost]->x;
        }
        my $p = $leftmost;
        my $q;
        do {
            $q = ($p + 1) % @$points;
            for my $j (0 .. @$points - 1) {
                $q = $j if _ccw($points->[$p], $points->[$j], $points->[$q]);
            }
            $next[$p] = $q;
            $p = $q;
        } while $p != $leftmost;

        display($points, \@next);
    }

    sub display {
        my ($points, $next) = @_;
        say "\nConvex Hull points:";

        for my $i (grep $next->[$_] != -1, 0 .. $#$next) {
            say '(', $points->[$i]->x, ', ', $points->[$i]->y, ')'
        }
    }
}

say 'Jarvis Algorithm Test';
say 'Enter number of points n:';
chomp( my $n = <> );
say "Enter $n x, y cordinates";
my @points;
while (@points < $n) {
    my ($x, $y) = split ' ', <>;
    push @points, 'Point'->new(x => $x, y => $y);
}

Jarvis::convexHull(\@points);