1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 |
- #!/usr/bin/perl
- # Author: Trizen
- # Date: 26 November 2023
- # https://github.com/trizen
- # Shortest Distance Among Points
- # https://projecteuler.net/problem=816
- # Runtime: 25.038s
- use 5.036;
- use ntheory qw(powmod);
- {
- my @cache;
- sub rng ($n) {
- $n == 0 && return 290797;
- $cache[$n] //= powmod(rng($n - 1), 2, 50515093);
- }
- }
- sub hypot ($a, $b) {
- sqrt($a**2 + $b**2);
- }
- sub d ($k) {
- my @P = map { [rng(2 * $_), rng(2 * $_ + 1)] } (1 .. $k);
- my @C1 = sort { $a->[0] <=> $b->[0] } @P;
- my @C2 = sort { $a->[1] <=> $b->[1] } @P;
- my $min_dist = 1e9**1e9;
- foreach my $i (0 .. $#C1 - 1) {
- my $p1 = $C1[$i];
- my $p2 = $C1[$i + 1];
- my $dist = hypot($p1->[0] - $p2->[0], $p1->[1] - $p2->[1]);
- if ($dist < $min_dist) {
- $min_dist = $dist;
- }
- }
- foreach my $i (0 .. $#C2 - 1) {
- my $p1 = $C2[$i];
- my $p2 = $C2[$i + 1];
- my $dist = hypot($p1->[0] - $p2->[0], $p1->[1] - $p2->[1]);
- if ($dist < $min_dist) {
- $min_dist = $dist;
- }
- }
- sprintf('%.9f', $min_dist);
- }
- d(14) eq '546446.466846479' or die "error";
- d(1000) eq '14759.650571745' or die "error";
- d(2000) eq '16462.444107726' or die "error";
- say d(2000000);
|