Closest-pair problem: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 1:
[[Category:Geometry]]▼
{{task|Classic CS problems and programs}}
{{Wikipedia|Closest pair of points problem}}
Line 67 ⟶ 68:
* [http://www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt Closest pair (IUPUI)]
<br><br>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Closest Pair Problem 10/03/2017
CLOSEST CSECT
USING CLOSEST,R13 base register
Line 205:
[ 0.925092, 0.818220]
</pre>
=={{header|Ada}}==
Dimension independent, but has to be defined at procedure call time
Line 212 ⟶ 211:
closest.adb: (uses brute force algorithm)
<syntaxhighlight lang=
with Ada.Text_IO;
Line 289 ⟶ 288:
P2: 9.25092E-01 8.18220E-01
Distance: 7.79101E-02</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang=
if (points.count() <= 3)
return bruteForceClosestPair(points)
Line 357 ⟶ 355:
}
;---------------------------------------------------------------</syntaxhighlight>
Examples:<syntaxhighlight lang=
MsgBox % ClosestPair(points)</syntaxhighlight>
{{out}}
<pre>1.000000</pre>
=={{header|AWK}}==
<syntaxhighlight lang=
# syntax: GAWK -f CLOSEST-PAIR_PROBLEM.AWK
BEGIN {
Line 395 ⟶ 392:
distance between (0.891663,0.888594) and (0.925092,0.818220) is 0.0779102
</pre>
=={{header|BASIC256}}==
'''Versión de fuerza bruta:
<syntaxhighlight lang=
Dim x(9)
x = {0.654682, 0.409382, 0.891663, 0.716629, 0.477721, 0.925092, 0.624291, 0.211332, 0.293786, 0.839186}
Line 418 ⟶ 414:
El par más cercano es 2 y 5 a una distancia de 0,077910191355
</pre>
=={{header|BBC BASIC}}==
To find the closest pair it is sufficient to compare the squared-distances,
it is not necessary to perform the square root for each pair!
<syntaxhighlight lang="bbcbasic"> DIM x(9), y(9)
FOR I% = 0 TO 9
Line 451 ⟶ 446:
{{out}}
<pre>Closest pair is 2 and 5 at distance 0.0779101913</pre>
=={{header|C}}==
See [[Closest-pair problem/C]]
=={{header|C sharp|C#}}==
We provide a small helper class for distance comparisons:
<syntaxhighlight lang="csharp">class Segment
{
public Segment(PointF p1, PointF p2)
Line 481 ⟶ 474:
Brute force:
<syntaxhighlight lang="csharp">Segment Closest_BruteForce(List<PointF> points)
{
int n = points.Count;
Line 495 ⟶ 488:
And divide-and-conquer.
<syntaxhighlight lang="csharp">
public static Segment MyClosestDivide(List<PointF> points)
{
Line 549 ⟶ 542:
However, the difference in speed is still remarkable.
<syntaxhighlight lang="csharp">var randomizer = new Random(10);
var points = Enumerable.Range( 0, 10000).Select( i => new PointF( (float)randomizer.NextDouble(), (float)randomizer.NextDouble())).ToList();
Stopwatch sw = Stopwatch.StartNew();
Line 566 ⟶ 559:
Non Linq Brute Force:
<syntaxhighlight lang="csharp">
Segment Closest_BruteForce(List<PointF> points)
{
Line 591 ⟶ 584:
Targeted Search: Much simpler than divide and conquer, and actually runs faster for the random points. Key optimization is that if the distance along the X axis is greater than the best total length you already have, you can terminate the inner loop early. However, as only sorts in the X direction, it degenerates into an N^2 algorithm if all the points have the same X.
<syntaxhighlight lang="csharp">
Segment Closest(List<PointF> points)
{
Line 627 ⟶ 620:
}
</syntaxhighlight>
=={{header|C++}}==
<syntaxhighlight lang="cpp">/*
Author: Kevin Bacon
Date: 04/03/2014
Line 748 ⟶ 740:
<pre>Min distance (brute): 6.95886 (932.735, 1002.7), (939.216, 1000.17)
Min distance (optimized): 6.95886 (932.735, 1002.7), (939.216, 1000.17)</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
(defn distance [[x1 y1] [x2 y2]]
(let [dx (- x2 x1), dy (- y2 y1)]
Line 789 ⟶ 780:
(combine yS [dmin pmin1 pmin2])))))
</syntaxhighlight>
=={{header|Common Lisp}}==
Points are conses whose cars are x coördinates and whose cdrs are y coördinates. This version includes the optimizations given in the [http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html McGill description] of the algorithm.
<syntaxhighlight lang="lisp">(defun point-distance (p1 p2)
(destructuring-bind (x1 . y1) p1
(destructuring-bind (x2 . y2) p2
Line 849 ⟶ 839:
(cp (sort (copy-list points) '< :key 'car))
(values pair distance))))</syntaxhighlight>
=={{header|Crystal}}==
=={{header|D}}==
===Compact Versions===
<syntaxhighlight lang="d">import std.stdio, std.typecons, std.math, std.algorithm,
std.random, std.traits, std.range, std.complex;
Line 937 ⟶ 925:
===Faster Brute-force Version===
<syntaxhighlight lang="d">import std.stdio, std.random, std.math, std.typecons, std.complex,
std.traits;
Line 979 ⟶ 967:
<pre>Closest pair: Distance: 0.019212 p1, p2: 9.74223+119.419i, 9.72306+119.418i</pre>
About 0.12 seconds run-time for brute-force version 2 (10_000 points) with with LDC2 compiler.
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Closest-pair_problem#Pascal Pascal].
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">defmodule Closest_pair do
# brute-force algorithm:
def bruteForce([p0,p1|_] = points), do: bf_loop(points, {distance(p0, p1), {p0, p1}})
Line 1,060 ⟶ 1,046:
{0.9399398976079764, 0.020522908141823986}}}}
</pre>
=={{header|F Sharp|F#}}==
Brute force:
<syntaxhighlight lang="fsharp">
let closest_pairs (xys: Point []) =
let n = xys.Length
Line 1,072 ⟶ 1,057:
</syntaxhighlight>
For example:
<syntaxhighlight lang="fsharp">
closest_pairs
[|Point(0.0, 0.0); Point(1.0, 0.0); Point (2.0, 2.0)|]
</syntaxhighlight>
gives:
<syntaxhighlight lang="fsharp">
(0,0, 1,0)
</syntaxhighlight>
Line 1,083 ⟶ 1,068:
Divide And Conquer:
<syntaxhighlight lang="fsharp">
open System;
Line 1,175 ⟶ 1,160:
printfn "Took %d [ms]" takenMs
</syntaxhighlight>
=={{header|Fantom}}==
(Based on the Ruby example.)
<syntaxhighlight lang="fantom">
class Point
{
Line 1,314 ⟶ 1,298:
Time taken: 228ms
</pre>
=={{header|Fortran}}==
See [[Closest pair problem/Fortran]]
=={{header|FreeBASIC}}==
'''Versión de fuerza bruta:
<syntaxhighlight lang="freebasic">
Dim As Integer i, j
Dim As Double minDist = 1^30
Line 1,358 ⟶ 1,340:
El par más cercano es 2 y 5 a una distancia de 0.07791019135517516
</pre>
=={{header|Go}}==
'''Brute force'''
<syntaxhighlight lang="go">package main
import (
Line 1,408 ⟶ 1,389:
}</syntaxhighlight>
'''O(n)'''
<syntaxhighlight lang="go">// implementation following algorithm described in
// http://www.cs.umd.edu/~samir/grant/cp.pdf
package main
Line 1,524 ⟶ 1,505:
return p1, p2
}</syntaxhighlight>
=={{header|Groovy}}==
Point class:
<syntaxhighlight lang="groovy">class Point {
final Number x, y
Point(Number x = 0, Number y = 0) { this.x = x; this.y = y }
Line 1,535 ⟶ 1,515:
Brute force solution. Incorporates X-only and Y-only pre-checks in two places to cut down on the square root calculations:
<syntaxhighlight lang="groovy">def bruteClosest(Collection pointCol) {
assert pointCol
List l = pointCol
Line 1,560 ⟶ 1,540:
Elegant (divide-and-conquer reduction) solution. Incorporates X-only and Y-only pre-checks in two places (four if you count the inclusion of the brute force solution) to cut down on the square root calculations:
<syntaxhighlight lang="groovy">def elegantClosest(Collection pointCol) {
assert pointCol
List xList = (pointCol as List).sort { it.x }
Line 1,610 ⟶ 1,590:
Benchmark/Test:
<syntaxhighlight lang="groovy">def random = new Random()
(1..4).each {
Line 1,694 ⟶ 1,674:
Speedup ratio (B/E): 26.3500255493
=========================================</pre>
=={{header|Haskell}}==
BF solution:
<syntaxhighlight lang=
import System.Random (newStdGen, randomRs)
Line 1,722 ⟶ 1,701:
</syntaxhighlight>
{{out}}
<syntaxhighlight lang=
([[0.8347201880148426,0.40774840545089647],[0.8348731214261784,0.4087113189531284]],9.749825850154334e-4)
(4.02 secs, 488869056 bytes)</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
This is a brute force solution.
It combines reading the points with computing the closest pair seen so far.
<syntaxhighlight lang="unicon">record point(x,y)
procedure main()
Line 1,754 ⟶ 1,732:
return (p2.x-p1.x)^2 + (p2.y-p1.y)^2 # (sufficient for closeness)
end</syntaxhighlight>
=={{header|IS-BASIC}}==
<syntaxhighlight lang=
110 NUMERIC X(1 TO 10),Y(1 TO 10)
120 FOR I=1 TO 10
Line 1,780 ⟶ 1,757:
320 DATA 0.293786,0.691701
330 DATA 0.839186,0.728260</syntaxhighlight>
=={{header|J}}==
Solution of the simpler (brute-force) problem:
<syntaxhighlight lang="j">vecl =: +/"1&.:*: NB. length of each vector
dist =: <@:vecl@:({: -"1 }:)\ NB. calculate all distances among vectors
minpair=: ({~ > {.@($ #: I.@,)@:= <./@;)dist NB. find one pair of the closest points
closestpairbf =: (; vecl@:-/)@minpair NB. the pair and their distance</syntaxhighlight>
Examples of use:
<syntaxhighlight lang="j"> ]pts=:10 2 ?@$ 0
0.654682 0.925557
0.409382 0.619391
Line 1,806 ⟶ 1,782:
+-----------------+---------+</syntaxhighlight>
The program also works for higher dimensional vectors:
<syntaxhighlight lang="j"> ]pts=:10 4 ?@$ 0
0.559164 0.482993 0.876 0.429769
0.217911 0.729463 0.97227 0.132175
Line 1,823 ⟶ 1,799:
|0.316673 0.797519 0.745821 0.0598321| |
+------------------------------------+--------+</syntaxhighlight>
=={{header|Java}}==
Line 1,829 ⟶ 1,804:
'''Code:'''
<syntaxhighlight lang=
public class ClosestPair
Line 2,021 ⟶ 1,996:
Brute force (1594 ms): (0.9246533850872104, 0.098709007587097)-(0.924591196030625, 0.09862206991823985) : 1.0689077146927108E-4
Divide and conquer (250 ms): (0.924591196030625, 0.09862206991823985)-(0.9246533850872104, 0.098709007587097) : 1.0689077146927108E-4</pre>
=={{header|JavaScript}}==
Using bruteforce algorithm, the ''bruteforceClosestPair'' method below expects an array of objects with x- and y-members set to numbers, and returns an object containing the members ''distance'' and ''points''.
<syntaxhighlight lang="javascript">function distance(p1, p2) {
var dx = Math.abs(p1.x - p2.x);
var dy = Math.abs(p1.y - p2.y);
Line 2,054 ⟶ 2,028:
divide-and-conquer method:
<syntaxhighlight lang="javascript">
var Point = function(x, y) {
Line 2,195 ⟶ 2,169:
</syntaxhighlight>
=={{header|jq}}==
{{works with|jq|1.4}}
Line 2,202 ⟶ 2,175:
'''Infrastructure''':
<syntaxhighlight lang="jq"># This definition of "until" is included in recent versions (> 1.4) of jq
# Emit the first input that satisfied the condition
def until(cond; next):
Line 2,212 ⟶ 2,185:
def dist(x;y):
[x[0] - y[0], x[1] - y[1]] | map(.*.) | add | sqrt;</syntaxhighlight>
<syntaxhighlight lang="jq">
# P is an array of points, [x,y].
# Emit the solution in the form [dist, [P1, P2]]
Line 2,267 ⟶ 2,240:
closestPair( sort_by(.[0]); sort_by(.[1])) ;</syntaxhighlight>
'''Example from the Mathematica section''':
<syntaxhighlight lang="jq">def data:
[[0.748501, 4.09624],
[3.00302, 5.26164],
Line 2,283 ⟶ 2,256:
$jq -M -c -n -f closest_pair.jq
[0.0894096443343775,[[7.46489,4.6268],[7.46911,4.71611]]]
=={{header|Julia}}==
{{works with|Julia|0.6}}
Brute-force algorithm:
<syntaxhighlight lang="julia">function closestpair(P::Vector{Vector{T}}) where T <: Number
N = length(P)
if N < 2 return (Inf, ()) end
Line 2,303 ⟶ 2,275:
closestpair([[0, -0.3], [1., 1.], [1.5, 2], [2, 2], [3, 3]])</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.1.2
typealias Point = Pair<Double, Double>
Line 2,393 ⟶ 2,364:
Closest pair (optimized) is (0.891663, 0.888594) and (0.925092, 0.81822), distance 0.07791019135517516
</pre>
=={{header|Liberty BASIC}}==
NB array terms can not be READ directly.
<syntaxhighlight lang="lb">
N =10
Line 2,441 ⟶ 2,411:
</syntaxhighlight>
Distance =0.77910191e-1 between ( 0.891663, 0.888594) and ( 0.925092, 0.81822)
=={{header|Maple}}==
<syntaxhighlight lang=
local
Line 2,514 ⟶ 2,483:
end module; #ClosestPair</syntaxhighlight>
{{out}}<syntaxhighlight lang=
> L := RandomTools:-Generate(list(list(float(range=0..1),2),512)):
> ClosestPair(L);
0.002576770304, [[0.4265584800, 0.7443097852], [0.4240649736, 0.7449595321]]
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
'''O(''n''<sup>2</sup>)'''
<syntaxhighlight lang=
Block[{pos, dist = N[Outer[EuclideanDistance, data, data, 1]]},
pos = Position[dist, Min[DeleteCases[Flatten[dist], 0.]]];
Line 2,528 ⟶ 2,496:
'''O(''n''<sup>2</sup>) output:'''
<syntaxhighlight lang=
9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,
8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,
Line 2,537 ⟶ 2,505:
''' O(''n''log ''n'') '''
<syntaxhighlight lang=
Module[{xP, yP,
pts},(*Top level function.Sorts the pts by x and by y and then \
Line 2,582 ⟶ 2,550:
''' O(''n''log''n'') output: '''
<syntaxhighlight lang=
9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,
8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,
Line 2,588 ⟶ 2,556:
{0.0894096, {{7.46489, 4.6268}, {7.46911, 4.71611}}}</syntaxhighlight>
=={{header|MATLAB}}==
This solution is an almost direct translation of the above pseudo-code into MATLAB.
<syntaxhighlight lang=
N = numel(xP);
Line 2,665 ⟶ 2,632:
{{out}}
<syntaxhighlight lang=
distance =
Line 2,675 ⟶ 2,642:
[1x2 double] [1x2 double] %The pair is [1.5 2] and [2 2] which is correct</syntaxhighlight>
=={{header|Microsoft Small Basic}}==
<syntaxhighlight lang="smallbasic">' Closest Pair Problem
s="0.654682,0.925557,0.409382,0.619391,0.891663,0.888594,0.716629,0.996200,0.477721,0.946355,0.925092,0.818220,0.624291,0.142924,0.211332,0.221507,0.293786,0.691701,0.839186,0.728260,"
i=0
Line 2,729 ⟶ 2,695:
[0.925092,0.818220]
</pre>
=={{header|Nim}}==
<syntaxhighlight lang=
type
Line 2,843 ⟶ 2,808:
Execution time for brute force algorithm: 2656 ms
Execution time for optimized algorithm: 63 ms</pre>
=={{header|Objective-C}}==
See [[Closest-pair problem/Objective-C]]
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">
type point = { x : float; y : float }
Line 2,975 ⟶ 2,938:
</syntaxhighlight>
=={{header|Oz}}==
Translation of pseudocode:
<syntaxhighlight lang="oz">declare
fun {Distance X1#Y1 X2#Y2}
{Sqrt {Pow X2-X1 2.0} + {Pow Y2-Y1 2.0}}
Line 3,077 ⟶ 3,039:
{Show Points}
{Show {ClosestPair Points}}</syntaxhighlight>
=={{header|PARI/GP}}==
Naive quadratic solution.
<syntaxhighlight lang="parigp">closestPair(v)={
my(r=norml2(v[1]-v[2]),at=[1,2]);
for(a=1,#v-1,
Line 3,092 ⟶ 3,053:
[v[at[1]],v[at[2]]]
};</syntaxhighlight>
=={{header|Pascal}}==
Brute force only calc square of distance, like AWK etc...
As fast as [[Closest-pair_problem#Faster_Brute-force_Version | D ]] .
<syntaxhighlight lang="pascal">program closestPoints;
{$IFDEF FPC}
{$MODE Delphi}
Line 3,178 ⟶ 3,138:
//32-Bit
PointCnt = { 10000*sqrt(10) } 31623;-> real 0m1.112s 10x times runtime</pre>
=={{header|Perl}}==
The divide & conquer technique is about 100x faster than the brute-force algorithm.
<syntaxhighlight lang="perl">use strict;
use warnings;
use POSIX qw(ceil);
Line 3,243 ⟶ 3,202:
<pre>0.00259322 between (-1.95541, -4.29695), (-1.95351, -4.29871)
0.00259322 between (-1.95541, -4.29695), (-1.95351, -4.29871)</pre>
=={{header|Phix}}==
Brute force and divide and conquer (translated from pseudocode) approaches compared
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
Line 3,351 ⟶ 3,309:
Closest pair: {0.0328051,0.0966250} {0.0328850,0.0966250}, distance=0.000120143 (0.14s)
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang=
(let Min T
(use (Pt1 Pt2)
Line 3,384 ⟶ 3,341:
(0.839186 . 0.728260) ) )
-> ((891663 . 888594) (925092 . 818220) 77910)</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="text">
/* Closest Pair Problem */
closest: procedure options (main);
Line 3,420 ⟶ 3,376:
end closest;
</syntaxhighlight>
=={{header|Prolog}}==
'''Brute force version, works with SWI-Prolog, tested on version 7.2.3.
<syntaxhighlight lang=
% main predicate, find and print closest point
do_find_closest_points(Points) :-
Line 3,456 ⟶ 3,411:
</syntaxhighlight>
To test, pass in a list of points.
<syntaxhighlight lang=
point(0.654682, 0.925557),
point(0.409382, 0.619391),
Line 3,477 ⟶ 3,432:
false.
</pre>
=={{header|PureBasic}}==
'''Brute force version
<syntaxhighlight lang=
Protected N=ArraySize(P()), i, j
Protected mindistance.f=Infinity(), t.d
Line 3,502 ⟶ 3,456:
Implementation can be as
<syntaxhighlight lang=
x.d
y.d
Line 3,537 ⟶ 3,491:
Press ENTER to quit</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">"""
Compute nearest pair of points using two algorithms
Line 3,681 ⟶ 3,634:
Time for closestPair 0.119326618327
>>> </pre></div>
=={{header|R}}==
{{works with|R|2.8.1+}}
Brute force solution as per wikipedia pseudo-code
<syntaxhighlight lang=
xy = cbind(x,y)
cp = bruteforce(xy)
Line 3,717 ⟶ 3,669:
Quicker brute force solution for R that makes use of the apply function native to R for dealing with matrices. It expects x and y to take the form of separate vectors.
<syntaxhighlight lang=
{
distancev <- function(pointsv)
Line 3,741 ⟶ 3,693:
This is the quickest version, that makes use of the 'dist' function of R. It takes a two-column object of x,y-values as input, or creates such an object from seperate x and y-vectors.
<syntaxhighlight lang=
# takes two-column object(x,y-values), or creates such an object from x and y values
if(!is.null(y)) x <- cbind(x, y)
Line 3,760 ⟶ 3,712:
}</syntaxhighlight>
Example<syntaxhighlight lang=
y = (sample(-1000.00:1000.00,length(x)))
cp = closest.pairs(x,y)
Line 3,800 ⟶ 3,752:
Using dist function for brute force, but divide and conquer (as per pseudocode) for speed:
<syntaxhighlight lang=
{
if (!is.null(y))
Line 3,922 ⟶ 3,874:
That took 6.38 seconds.
</pre>
=={{header|Racket}}==
The brute force solution using complex numbers
to represent pairs.
<syntaxhighlight lang="racket">
#lang racket
(define (dist z0 z1) (magnitude (- z1 z0)))
Line 3,945 ⟶ 3,896:
The divide and conquer algorithm using a struct to represent points
<syntaxhighlight lang="racket">
#lang racket
(struct point (x y) #:transparent)
Line 4,046 ⟶ 3,997:
{{out}}
<syntaxhighlight lang="racket">
Closest points: (0+1i 1+2i)
Distance: 1.4142135623730951
Line 4,052 ⟶ 4,003:
Closest points on a quadratic curve (0,0) (1,1)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
Line 4,059 ⟶ 4,009:
Using concurrency, the 'simple' routine beats the (supposedly) more efficient one for all but the smallest sets of input.
<syntaxhighlight lang="raku" line>sub MAIN ($N = 5000) {
my @points = (^$N).map: { [rand × 20 - 10, rand × 20 - 10] }
Line 4,111 ⟶ 4,061:
<pre>simple (([-1.1560800527301716 -9.214015073077793] [-1.1570263876019649 -9.213340680530798] 0.0011620477602117762))
real (([-1.1570263876019649 -9.213340680530798] [-1.1560800527301716 -9.214015073077793] 0.0011620477602117762))</pre>
=={{header|REXX}}==
Programming note: this REXX version allows two (or more) points to be identical, and will
<br>manifest itself as a minimum distance of zero (the variable <big> <tt> '''dd''' </tt> </big> on line 17).
<syntaxhighlight lang="rexx">/*REXX program solves the closest pair of points problem (in two dimensions). */
parse arg N LO HI seed . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 100 /*Not specified? Then use the default.*/
Line 4,165 ⟶ 4,114:
[ 6263, 19108]
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
decimals(10)
x = list(10)
Line 4,205 ⟶ 4,153:
closest pair is : 3 and 6 at distance 0.0779101914
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">Point = Struct.new(:x, :y)
def distance(p1, p2)
Line 4,268 ⟶ 4,215:
recursive 0.187000 0.000000 0.187000 ( 0.190000)
</pre>
=={{header|Run BASIC}}==
Courtesy http://dkokenge.com/rbp
<syntaxhighlight lang="runbasic">n =10 ' 10 data points input
dim x(n)
dim y(n)
Line 4,312 ⟶ 4,258:
data 0.293786, 0.691701
data 0.839186, 0.72826</syntaxhighlight>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
//! We interpret complex numbers as points in the Cartesian plane, here. We also use the
//! [sweepline/plane sweep closest pairs algorithm][algorithm] instead of the divide-and-conquer
Line 4,439 ⟶ 4,384:
Distance: 0.07791013
</pre>
=={{header|Scala}}==
<syntaxhighlight lang=
import scala.util.Random
Line 4,582 ⟶ 4,526:
Divide and conquer (52 ms): (0.4198255166110827, 0.45044969701435)-(0.41984960343173994, 0.4499078600557793) : 5.423720721077961E-4
</pre>
=={{header|Seed7}}==
This is the brute force algorithm:
<syntaxhighlight lang="seed7">const type: point is new struct
var float: x is 0.0;
var float: y is 0.0;
Line 4,619 ⟶ 4,562:
end if;
end func;</syntaxhighlight>
=={{header|Sidef}}==
{{trans|Raku}}
<syntaxhighlight lang="ruby">func dist_squared(a, b) {
sqr(a[0] - b[0]) + sqr(a[1] - b[1])
}
Line 4,693 ⟶ 4,635:
var (af, bf, df) = closest_pair(points)
say "#{df} at (#{af.join(' ')}), (#{bf.join(' ')})"</syntaxhighlight>
=={{header|Smalltalk}}==
See [[Closest-pair problem/Smalltalk]]
=={{header|Swift}}==
<syntaxhighlight lang="swift">import Foundation
struct Point {
Line 4,803 ⟶ 4,743:
<pre>(Point(x: 5.279430517795172, y: 8.85108182685002), Point(x: 5.278427575530877, y: 8.851990433099456))</pre>
=={{header|Tcl}}==
Each point is represented as a list of two floating-point numbers, the first being the ''x'' coordinate, and the second being the ''y''.
<syntaxhighlight lang=
# retrieve the x-coordinate
Line 4,901 ⟶ 4,840:
recursive 14613 488094 0.0015652738546658382</pre>
Note that the <code>lindex</code> and <code>llength</code> commands are both O(1).
=={{header|Ursala}}==
The brute force algorithm is easy.
Line 4,911 ⟶ 4,849:
each remaining pair the sum of the squares of the differences
between corresponding coordinates.
<syntaxhighlight lang=
clop = @iiK0 fleq$-&l+ *EZF ^\~& plus+ sqr~~+ minus~~bbI</syntaxhighlight>
Line 4,918 ⟶ 4,856:
The <code>eudist</code> library function
is used to compute the distance between points.
<syntaxhighlight lang=
#import flo
Line 4,927 ⟶ 4,865:
^/~&ar @farlK30K31XPGbrlrjX3J ^/~&arlhh @W lesser fleq@bl+-</syntaxhighlight>
test program:
<syntaxhighlight lang=
<
Line 4,959 ⟶ 4,897:
(-1.745694e+00,3.276434e+00))
</pre>
=={{header|VBA}}==
<syntaxhighlight lang="vb">Option Explicit
Private Type MyPoint
Line 5,036 ⟶ 4,973:
dist : 2,445694
--------------------------------------------------</pre>
=={{header|Visual FoxPro}}==
<syntaxhighlight lang="vfp">
CLOSE DATABASES ALL
CREATE CURSOR pairs(id I, xcoord B(6), ycoord B(6))
Line 5,067 ⟶ 5,003:
Distance is 0.077910.
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="ecmascript">import "/math" for Math
import "/sort" for Sort
Line 5,166 ⟶ 5,101:
Closest pair (optimized) is [0.891663, 0.888594] and [0.925092, 0.81822], distance 0.077910191355175
</pre>
=={{header|XPL0}}==
The brute force method is simpler than the recursive solution
and is perfectly adequate, even for a thousand points.
<syntaxhighlight lang=
proc ClosestPair(P, N); \Show closest pair of points in array P
Line 5,214 ⟶ 5,148:
0.891663,0.888594 -- 0.925092,0.818220
</pre>
=={{header|Yabasic}}==
'''Versión de fuerza bruta:
<syntaxhighlight lang=
minDist = 1^30
dim x(9), y(9)
Line 5,249 ⟶ 5,181:
El par mas cercano es 2 y 5 a una distancia de 3.68449e-05
</pre>
=={{header|zkl}}==
An ugly solution in both time and space.
<syntaxhighlight lang="zkl">class Point{
fcn init(_x,_y){ var[const] x=_x, y=_y; }
fcn distance(p){ (p.x-x).hypot(p.y-y) }
Line 5,268 ⟶ 5,198:
});
}</syntaxhighlight>
<syntaxhighlight lang="zkl">points:=T( 5.0, 9.0, 9.0, 3.0,
2.0, 0.0, 8.0, 4.0,
7.0, 4.0, 9.0, 10.0,
Line 5,288 ⟶ 5,218:
L(Point(0.925092,0.81822),Point(0.891663,0.888594),0.0779102)
</pre>
=={{header|ZX Spectrum Basic}}==
{{trans|BBC_BASIC}}
<syntaxhighlight lang="zxbasic">10 DIM x(10): DIM y(10)
20 FOR i=1 TO 10
30 READ x(i),y(i)
Line 5,314 ⟶ 5,243:
220 DATA 0.293786,0.691701
230 DATA 0.839186,0.728260</syntaxhighlight>
▲[[Category:Geometry]]
| |||