123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 26 November 2023
- # https://github.com/trizen
- # Shortest Distance Among Points
- # https://projecteuler.net/problem=816
- # Runtime: 4 minutes, 19 seconds
- func rng(n) is cached {
- n == 0 && return 290797
- powmod(__FUNC__(n-1), 2, 50515093)
- }
- func d(k) {
- var P = k.of {|n|
- [rng(2*n), rng(2*n + 1)]
- }
- var C1 = P.sort_by{ .head }
- var C2 = P.sort_by{ .tail }
- var min_dist = Inf
- C1.each_cons(2, {|a,b|
- var dist = hypot(a[0] - b[0], a[1] - b[1])
- if (dist < min_dist) {
- min_dist = dist
- }
- })
- C2.each_cons(2, {|a,b|
- var dist = hypot(a[0] - b[0], a[1] - b[1])
- if (dist < min_dist) {
- min_dist = dist
- }
- })
- return min_dist.round(-9)
- }
- assert_eq(d(14), 546446.466846479f)
- assert_eq(d(1000), 14759.650571745f)
- assert_eq(d(2000), 16462.444107726f)
- say d(2000000)
|