#!/usr/bin/env perl
use strict;
use Data::Dumper;
use Time::HiRes qw(gettimeofday tv_interval);
my $points = shift @ARGV;
my @points = read_points($points);
my $start = [gettimeofday];
my ($x, $y) = shortest_distance(@points);
my $end = [gettimeofday];
report($x, $y, $points, tv_interval($start, $end));
#This is the main loop, everything else is fluff.
sub shortest_distance {
my @points = @_;
my $points = @points;
my $min_distance = 4294967296;
my @min;
for (my $i = 0 ; $i < $points ; $i++) {
for (my $j = 0 ; $j < $points ; $j++) {
#this does not need to check the same point
# skip where j==i
my $d = distance($points[$i], $points[$j]); # sqrt(a2 + b2) not necessary... just smallest (diff x * diff y) is needed, then do sqrt(a2+b2)
#use a hash.... and insert x coordinates that are the same...
# push(@{ $foo{$x} }, $y);... but do you find the distance on insert?
# this doesn't need to check if d>0, duplicate coordinates are treated as one
if ($d > 0 && $d <= $min_distance) {
$min_distance = $d;
@min = ($i, $j);
}
}
}
return @min;
}
sub distance {
my ($a, $b) = @_;
my $d =
sqrt((abs($a->[0] - $b->[0])**2) + (abs($a->[1] - $b->[1])**2));
}
sub report {
my ($x, $y, $points, $time) = @_;
print "The minimum distance is between point $x and $y\n";
print "$x: $points[$x][0], $points[$x][1]\n";
print "$y: $points[$y][0], $points[$y][1]\n";
print "Distance: ", distance($points[$x], $points[$y]), "\n";
print "Took $time seconds\n";
print "At a rate of ", $time/$points ," sec/point\n";
}
use constant MAX => 255;
sub read_points {
my $cnt = shift;
my @p;
open (my $p, ">", "points.txt");
my $i = 0;
while ($i < $cnt) {
my $x = int(rand(MAX));
my $y = int(rand(MAX));
push @p, [$x, $y];
print $p "$i: $x, $y\n";
$i++;
}
print "We have ", scalar(@p), " points\n";
close($p);
return @p;
}