x y z

1 1 3
1 4 6
1 2 10

2 4 9
2 6 10
2 5 20

4 2 8
4 8 20
4 1 3

##</code><code>##

x y z

1 2 10
2 4 9
4 8 20


##</code><code>##

#!/usr/bin/perl

use strict;
use warnings;

my @AoA; # an array of arrays to represent the points.

while(<DATA>) {
	push @AoA, [ split ];
}

my @sorted = sort { $a->[1] <=> $b->[1] } @AoA; # thanks moritz!

=head
for my $aref ( @sorted ) {
	print "\t [ @$aref ],\n";
}
=cut

# implementing the Gift Wrap algorithm.
# the @sorted array contains all the points and that too in the sorted order
# the sorting helps identify the "left most point".

my (@P, @endPoint, @pointOnHull, $i, $flag1, $flag2);
@pointOnHull = @{$sorted[0]}; # the "left most point"
$i = 0;

do {
	$P[$i] = [ @pointOnHull ];
	@endPoint = @{$sorted[0]};
	for my $j (1 .. $#sorted) {
		
		# determine position of j'th element relative to line P[i] to P[endPoint]
		# it should lie to the right of the line P[i] to P[endPoint]
		# we check that if the current point's x and y co-ordinates
		# are greater than, in every respect, the current end point.
		
		if(${$sorted[$j]}[0] > $endPoint[0] && ${$sorted[$j]}[1] >= $endPoint[1]) {
			$flag1 = 1;
		}
		# check if the current end point is not a point on the hull.
		
		if($endPoint[0] != $pointOnHull[0] && $endPoint[1] != $pointOnHull[1]){
			$flag2 = 1;
		}
		
		if($flag1 || $flag2) {
			@endPoint = @{$sorted[$j]};
		}
	}
	$i++;
	@pointOnHull = @endPoint;
} until ($endPoint[0] == ${$P[0]}[0] && $endPoint[1] == ${$P[0]}[1]);

# Array P is the convex hull

for my $aref ( @P ) {
	print "\t [ @$aref ],\n";
}

__DATA__
20 50
50 10
43 45
23 46
48 93
324 45
245 437
2315 4576
135 457