Closest-pair problem: Difference between revisions
PascalABC.NET
mNo edit summary |
(PascalABC.NET) |
||
(44 intermediate revisions by 20 users not shown) | |||
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}}==
<
CLOSEST CSECT
USING CLOSEST,R13 base register
Line 198 ⟶ 197:
PG DS CL80
YREGS
END CLOSEST</
{{out}}
<pre>
Line 206 ⟶ 205:
[ 0.925092, 0.818220]
</pre>
=={{header|Ada}}==
Dimension independent, but has to be defined at procedure call time
Line 214 ⟶ 211:
closest.adb: (uses brute force algorithm)
<
with Ada.Text_IO;
Line 280 ⟶ 277:
Ada.Text_IO.Put_Line ("P2: " & Float'Image (Second_Points (2) (1)) & " " & Float'Image (Second_Points (2) (2)));
Ada.Text_IO.Put_Line ("Distance: " & Float'Image (Distance (Second_Points (1), Second_Points (2))));
end Closest;</
{{out}}
Line 291 ⟶ 288:
P2: 9.25092E-01 8.18220E-01
Distance: 7.79101E-02</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">ClosestPair(points){
if (points.count() <= 3)
return bruteForceClosestPair(points)
split := xSplit(Points)
LP := split.1 ; left points
LD := ClosestPair(LP) ; recursion : left closest pair
RP := split.2 ; right points
RD := ClosestPair(RP) ; recursion : right closest pair
minD := min(LD, RD) ; minimum of LD & RD
xmin := Split.3 - minD ; strip left boundary
xmax := Split.3 + minD ; strip right boundary
S := strip(points, xmin, xmax)
if (s.count()>=2)
{
SD := ClosestPair(S) ; recursion : strip closest pair
return min(SD, minD)
}
return minD
}
;---------------------------------------------------------------
strip(points, xmin, xmax){
strip:=[]
for i, coord in points
if (coord.1 >= xmin) && (coord.1 <= xmax)
strip.push([coord.1, coord.2])
return strip
}
;---------------------------------------------------------------
bruteForceClosestPair(points){
minD := []
loop, % points.count()-1{
p1 := points.RemoveAt(1)
loop, % points.count(){
p2 := points[A_Index]
d := dist(p1, p2)
minD.push(d)
}
}
return min(minD*)
}
;---------------------------------------------------------------
dist(p1, p2){
return Sqrt((p2.1-p1.1)**2 + (p2.2-p1.2)**2)
}
;---------------------------------------------------------------
xSplit(Points){
xL := [], xR := []
p := xSort(Points)
Loop % Ceil(p.count()/2)
xL.push(p.RemoveAt(1))
while p.count()
xR.push(p.RemoveAt(1))
mid := (xL[xl.count(),1] + xR[1,1])/2
return [xL, xR, mid]
}
;---------------------------------------------------------------
xSort(Points){
S := [], Res :=[]
for i, coord in points
S[coord.1, coord.2] := true
for x, coord in S
for y, v in coord
res.push([x, y])
return res
}
;---------------------------------------------------------------</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">points := [[1, 1], [12, 30], [40, 50], [5, 1], [12, 10], [3, 4], [17,25], [45,50],[51,34],[2,1],[2,2],[10,10]]
MsgBox % ClosestPair(points)</syntaxhighlight>
{{out}}
<pre>1.000000</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f CLOSEST-PAIR_PROBLEM.AWK
BEGIN {
Line 320 ⟶ 387:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 326 ⟶ 393:
</pre>
=={{header|
==={{header|BASIC256}}===
'''Versión de fuerza bruta:
<syntaxhighlight lang="basic256">
Dim x(9)
x = {0.654682, 0.409382, 0.891663, 0.716629, 0.477721, 0.925092, 0.624291, 0.211332, 0.293786, 0.839186}
Dim y(9)
y = {0.925557, 0.619391, 0.888594, 0.996200, 0.946355, 0.818220, 0.142924, 0.221507, 0.691701, 0.728260}
minDist = 1^30
For i = 0 To 8
For j = i+1 To 9
dist = (x[i] - x[j])^2 + (y[i] - y[j])^2
If dist < minDist Then minDist = dist : minDisti = i : minDistj = j
Next j
Next i
Print "El par más cercano es "; minDisti; " y "; minDistj; " a una distancia de "; Sqr(minDist)
End
</syntaxhighlight>
{{out}}
<pre>
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!
<
FOR I% = 0 TO 9
Line 355 ⟶ 446:
DATA 0.293786, 0.691701
DATA 0.839186, 0.728260
</syntaxhighlight>
{{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)
{
P1 = p1;
P2 = p2;
}
public readonly PointF P1;
public readonly PointF P2;
public float Length()
{
return (float)Math.Sqrt(LengthSquared());
}
public float LengthSquared()
{
return (P1.X - P2.X) * (P1.X - P2.X)
+ (P1.Y - P2.Y) * (P1.Y - P2.Y);
}
}</syntaxhighlight>
Brute force:
<syntaxhighlight lang="csharp">Segment Closest_BruteForce(List<PointF> points)
{
int n = points.Count;
var result = Enumerable.Range( 0, n-1)
.SelectMany( i => Enumerable.Range( i+1, n-(i+1) )
.Select( j => new Segment( points[i], points[j] )))
.OrderBy( seg => seg.LengthSquared())
.First();
return result;
}</syntaxhighlight>
And divide-and-conquer.
<syntaxhighlight lang="csharp">
public static Segment MyClosestDivide(List<PointF> points)
{
return MyClosestRec(points.OrderBy(p => p.X).ToList());
}
private static Segment MyClosestRec(List<PointF> pointsByX)
{
int count = pointsByX.Count;
if (count <= 4)
return Closest_BruteForce(pointsByX);
// left and right lists sorted by X, as order retained from full list
var leftByX = pointsByX.Take(count/2).ToList();
var leftResult = MyClosestRec(leftByX);
var rightByX = pointsByX.Skip(count/2).ToList();
var rightResult = MyClosestRec(rightByX);
var result = rightResult.Length() < leftResult.Length() ? rightResult : leftResult;
// There may be a shorter distance that crosses the divider
// Thus, extract all the points within result.Length either side
var midX = leftByX.Last().X;
var bandWidth = result.Length();
var inBandByX = pointsByX.Where(p => Math.Abs(midX - p.X) <= bandWidth);
// Sort by Y, so we can efficiently check for closer pairs
var inBandByY = inBandByX.OrderBy(p => p.Y).ToArray();
int iLast = inBandByY.Length - 1;
for (int i = 0; i < iLast; i++ )
{
var pLower = inBandByY[i];
for (int j = i + 1; j <= iLast; j++)
{
var pUpper = inBandByY[j];
// Comparing each point to successivly increasing Y values
// Thus, can terminate as soon as deltaY is greater than best result
if ((pUpper.Y - pLower.Y) >= result.Length())
break;
if (Segment.Length(pLower, pUpper) < result.Length())
result = new Segment(pLower, pUpper);
}
}
return result;
}
</syntaxhighlight>
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();
var r1 = Closest_BruteForce(points);
sw.Stop();
Debugger.Log(1, "", string.Format("Time used (Brute force) (float): {0} ms", sw.Elapsed.TotalMilliseconds));
Stopwatch sw2 = Stopwatch.StartNew();
var result2 = Closest_Recursive(points);
sw2.Stop();
Debugger.Log(1, "", string.Format("Time used (Divide & Conquer): {0} ms",sw2.Elapsed.TotalMilliseconds));
Assert.Equal(r1.Length(), result2.Length());</syntaxhighlight>
{{out}}
<pre>Time used (Brute force) (float): 145731.8935 ms
Time used (Divide & Conquer): 1139.2111 ms</pre>
Non Linq Brute Force:
<syntaxhighlight lang="csharp">
Segment Closest_BruteForce(List<PointF> points)
{
Trace.Assert(points.Count >= 2);
int count = points.Count;
// Seed the result - doesn't matter what points are used
// This just avoids having to do null checks in the main loop below
var result = new Segment(points[0], points[1]);
var bestLength = result.Length();
for (int i = 0; i < count; i++)
for (int j = i + 1; j < count; j++)
if (Segment.Length(points[i], points[j]) < bestLength)
{
result = new Segment(points[i], points[j]);
bestLength = result.Length();
}
return result;
}</syntaxhighlight>
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)
{
Trace.Assert(points.Count >= 2);
int count = points.Count;
points.Sort((lhs, rhs) => lhs.X.CompareTo(rhs.X));
var result = new Segment(points[0], points[1]);
var bestLength = result.Length();
for (int i = 0; i < count; i++)
{
var from = points[i];
for (int j = i + 1; j < count; j++)
{
var to = points[j];
var dx = to.X - from.X;
if (dx >= bestLength)
{
break;
}
if (Segment.Length(from, to) < bestLength)
{
result = new Segment(from, to);
bestLength = result.Length();
}
}
}
return result;
}
</syntaxhighlight>
=={{header|C++}}==
<
Author: Kevin Bacon
Date: 04/03/2014
Line 477 ⟶ 738:
print_point(answer.second.second);
return 0;
}</
{{out}}
<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}}==
<
(defn distance [[x1 y1] [x2 y2]]
(let [dx (- x2 x1), dy (- y2 y1)]
Line 522 ⟶ 782:
{yS true} (group-by (fn [[px _]] (< (Math/abs (- xm px)) dmin)) yP)]
(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.
<
(destructuring-bind (x1 . y1) p1
(destructuring-bind (x2 . y2) p2
Line 582 ⟶ 841:
(multiple-value-bind (pair distance)
(cp (sort (copy-list points) '< :key 'car))
(values pair distance))))</
=={{header|Crystal}}==
=={{header|D}}==
===Compact Versions===
<
std.random, std.traits, std.range, std.complex;
Line 834 ⟶ 918:
writeln("bruteForceClosestPair: ", points.bruteForceClosestPair);
writeln(" closestPair: ", points.closestPair);
}</
{{out}}
<pre>[5+9i, 9+3i, 2+0i, 8+4i, 7+4i, 9+10i, 1+9i, 8+2i, 0+10i, 9+6i]
Line 844 ⟶ 928:
===Faster Brute-force Version===
<
std.traits;
Line 882 ⟶ 966:
writefln("Closest pair: Distance: %f p1, p2: %f, %f",
abs(pts[ij[0]] - pts[ij[1]]), pts[ij[0]], pts[ij[1]]);
}</
{{out}}
<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|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight>
# bruteforce
numfmt 4 0
x[] = [ 0.654682 0.409382 0.891663 0.716629 0.477721 0.925092 0.624291 0.211332 0.293786 0.839186 ]
y[] = [ 0.925557 0.619391 0.888594 0.996200 0.946355 0.818220 0.142924 0.221507 0.691701 0.728260 ]
n = len x[]
min = 1 / 0
for i to n - 1
for j = i + 1 to n
dx = x[i] - x[j]
dy = y[i] - y[j]
dsq = dx * dx + dy * dy
if dsq < min
min = dsq
mini = i
minj = j
.
.
.
print "distance between (" & x[mini] & " " & y[mini] & ") and (" & x[minj] & " " & y[minj] & ") is " & sqrt min
</syntaxhighlight>
=={{header|Elixir}}==
<
# brute-force algorithm:
def bruteForce([p0,p1|_] = points), do: bf_loop(points, {distance(p0, p1), {p0, p1}})
Line 946 ⟶ 1,055:
IO.inspect :timer.tc(fn -> Closest_pair.bruteForce(data2) end)
IO.puts "Recursive divide&conquer:"
IO.inspect :timer.tc(fn -> Closest_pair.recursive(data2) end)</
{{out}}
Line 967 ⟶ 1,076:
=={{header|F Sharp|F#}}==
Brute force:
<
let closest_pairs (xys: Point []) =
let n = xys.Length
Line 974 ⟶ 1,083:
yield xys.[i], xys.[j] }
|> Seq.minBy (fun (p0, p1) -> (p1 - p0).LengthSquared)
</syntaxhighlight>
For example:
<
closest_pairs
[|Point(0.0, 0.0); Point(1.0, 0.0); Point (2.0, 2.0)|]
</syntaxhighlight>
gives:
<
(0,0, 1,0)
</syntaxhighlight>
Divide And Conquer:
<
open System;
Line 1,078 ⟶ 1,187:
printfn "Closest Pair '%A'. Distance %f" closest (Length closest)
printfn "Took %d [ms]" takenMs
</syntaxhighlight>
=={{header|Fantom}}==
(Based on the Ruby example.)
<
class Point
{
Line 1,203 ⟶ 1,311:
}
}
</syntaxhighlight>
{{out}}
Line 1,218 ⟶ 1,326:
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
Dim As Double x(9), y(9), dist, mini, minj
Data 0.654682, 0.925557
Data 0.409382, 0.619391
Data 0.891663, 0.888594
Data 0.716629, 0.996200
Data 0.477721, 0.946355
Data 0.925092, 0.818220
Data 0.624291, 0.142924
Data 0.211332, 0.221507
Data 0.293786, 0.691701
Data 0.839186, 0.728260
For i = 0 To 9
Read x(i), y(i)
Next i
For i = 0 To 8
For j = i+1 To 9
dist = (x(i) - x(j))^2 + (y(i) - y(j))^2
If dist < minDist Then
minDist = dist
mini = i
minj = j
End If
Next j
Next i
Print "El par más cercano es "; mini; " y "; minj; " a una distancia de "; Sqr(minDist)
End
</syntaxhighlight>
{{out}}
<pre>
El par más cercano es 2 y 5 a una distancia de 0.07791019135517516
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_elements = 9
local fn ClosetPairProblem
long i, j
double minDist = 1000000
double dist, minDisti, minDistj
double x(_elements), y(_elements)
x(0) = 0.654682 : y(0) = 0.925557
x(1) = 0.409382 : y(1) = 0.619391
x(2) = 0.891663 : y(2) = 0.888594
x(3) = 0.716629 : y(3) = 0.996200
x(4) = 0.477721 : y(4) = 0.946355
x(5) = 0.925092 : y(5) = 0.818220
x(6) = 0.624291 : y(6) = 0.142924
x(7) = 0.211332 : y(7) = 0.221507
x(8) = 0.293786 : y(8) = 0.691701
x(9) = 0.839186 : y(9) = 0.728260
for i = 0 to 8
for j = i + 1 to 9
dist = ( x(i) - x(j) )^2 + ( y(i) - y(j) )^2
if dist < minDist then minDist = dist : minDisti = i : minDistj = j
next
next
print "The closest pair is "; minDisti; " and "; minDistj; " at a distance of "; sqr(minDist)
end fn
fn ClosetPairProblem
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
The closest pair is 2 and 5 at a distance of 0.07791019135517516
</pre>
=={{header|Go}}==
'''Brute force'''
<
import (
Line 1,269 ⟶ 1,458:
}
return
}</
'''O(n)'''
<
// http://www.cs.umd.edu/~samir/grant/cp.pdf
package main
Line 1,386 ⟶ 1,575:
}
return p1, p2
}</
=={{header|Groovy}}==
Point class:
<
final Number x, y
Point(Number x = 0, Number y = 0) { this.x = x; this.y = y }
Number distance(Point that) { ((this.x - that.x)**2 + (this.y - that.y)**2)**0.5 }
String toString() { "{x:${x}, y:${y}}" }
}</
Brute force solution. Incorporates X-only and Y-only pre-checks in two places to cut down on the square root calculations:
<
assert pointCol
List l = pointCol
Line 1,420 ⟶ 1,608:
}
answer
}</
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:
<
assert pointCol
List xList = (pointCol as List).sort { it.x }
Line 1,470 ⟶ 1,658:
}
answer
}</
Benchmark/Test:
<
(1..4).each {
Line 1,500 ⟶ 1,688:
=========================================
"""
}</
Results:
Line 1,557 ⟶ 1,745:
Speedup ratio (B/E): 26.3500255493
=========================================</pre>
=={{header|Haskell}}==
BF solution:
<
import System.Random (newStdGen, randomRs)
Line 1,583 ⟶ 1,770:
foldl1'' = foldl1'
</syntaxhighlight>
{{out}}
<
([[0.8347201880148426,0.40774840545089647],[0.8348731214261784,0.4087113189531284]],9.749825850154334e-4)
(4.02 secs, 488869056 bytes)</
=={{header|Icon}} and {{header|Unicon}}==
This is a brute force solution.
It combines reading the points with computing the closest pair seen so far.
<
procedure main()
Line 1,616 ⟶ 1,802:
procedure dSquared(p1,p2) # Compute the square of the distance
return (p2.x-p1.x)^2 + (p2.y-p1.y)^2 # (sufficient for closeness)
end</
=={{header|IS-BASIC}}==
<syntaxhighlight lang="is-basic">100 PROGRAM "Closestp.bas"
110 NUMERIC X(1 TO 10),Y(1 TO 10)
120 FOR I=1 TO 10
130 READ X(I),Y(I)
140 PRINT X(I),Y(I)
150 NEXT
160 LET MN=INF
170 FOR I=1 TO 9
180 FOR J=I+1 TO 10
190 LET DSQ=(X(I)-X(J))^2+(Y(I)-Y(J))^2
200 IF DSQ<MN THEN LET MN=DSQ:LET MINI=I:LET MINJ=J
210 NEXT
220 NEXT
230 PRINT "Closest pair is (";X(MINI);",";Y(MINI);") and (";X(MINJ);",";Y(MINJ);")":PRINT "at distance";SQR(MN)
240 DATA 0.654682,0.925557
250 DATA 0.409382,0.619391
260 DATA 0.891663,0.888594
270 DATA 0.716629,0.996200
280 DATA 0.477721,0.946355
290 DATA 0.925092,0.818220
300 DATA 0.624291,0.142924
310 DATA 0.211332,0.221507
320 DATA 0.293786,0.691701
330 DATA 0.839186,0.728260</syntaxhighlight>
=={{header|J}}==
Solution of the simpler (brute-force) problem:
<
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</
Examples of use:
<
0.654682 0.925557
0.409382 0.619391
Line 1,641 ⟶ 1,851:
|0.891663 0.888594|0.0779104|
|0.925092 0.81822| |
+-----------------+---------+</
The program also works for higher dimensional vectors:
<
0.559164 0.482993 0.876 0.429769
0.217911 0.729463 0.97227 0.132175
Line 1,659 ⟶ 1,869:
|0.217911 0.729463 0.97227 0.132175|0.708555|
|0.316673 0.797519 0.745821 0.0598321| |
+------------------------------------+--------+</
=={{header|Java}}==
Line 1,666 ⟶ 1,875:
'''Code:'''
<
public class ClosestPair
Line 1,851 ⟶ 2,060:
System.out.println("MISMATCH");
}
}</
{{out}}
Line 1,858 ⟶ 2,067:
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''.
<
var dx = Math.abs(p1.x - p2.x);
var dy = Math.abs(p1.y - p2.y);
Line 1,888 ⟶ 2,096:
};
}
}</
divide-and-conquer method:
<
var Point = function(x, y) {
Line 2,031 ⟶ 2,239:
console.log(JSON.stringify(closestPair(Px, Py))); // {"distance":65.06919393998976,"pair":[{"x":37134,"y":1963},{"x":37181,"y":2008}]}
</syntaxhighlight>
=={{header|jq}}==
{{works with|jq|1.4}}
Line 2,039 ⟶ 2,246:
'''Infrastructure''':
<
# Emit the first input that satisfied the condition
def until(cond; next):
Line 2,048 ⟶ 2,255:
# Euclidean 2d distance
def dist(x;y):
[x[0] - y[0], x[1] - y[1]] | map(.*.) | add | sqrt;</
<syntaxhighlight lang="jq">
# P is an array of points, [x,y].
# Emit the solution in the form [dist, [P1, P2]]
Line 2,102 ⟶ 2,309:
| .[1]
end;
closestPair( sort_by(.[0]); sort_by(.[1])) ;</
'''Example from the Mathematica section''':
<
[[0.748501, 4.09624],
[3.00302, 5.26164],
Line 2,116 ⟶ 2,323:
[1.45428, 0.087596] ];
data | closest_pair</
{{Out}}
$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:
<
N = length(P)
if N < 2 return (Inf, ()) end
Line 2,139 ⟶ 2,345:
end
closestpair([[0, -0.3], [1., 1.], [1.5, 2], [2, 2], [3, 3]])</
=={{header|Kotlin}}==
<
typealias Point = Pair<Double, Double>
Line 2,220 ⟶ 2,425:
println("Closest pair (optimized) is ${pair2.first} and ${pair2.second}, distance $dist2\n")
}
}</
{{out}}
Line 2,230 ⟶ 2,435:
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,276 ⟶ 2,480:
data 0.839186, 0.72826
</syntaxhighlight>
Distance =0.77910191e-1 between ( 0.891663, 0.888594) and ( 0.925092, 0.81822)
=={{header|Maple}}==
<syntaxhighlight lang="maple">ClosestPair := module()
local
ModuleApply := proc(L::list,$)
local Lx, Ly, out;
Ly := sort(L, 'key'=(i->i[2]), 'output'='permutation');
Lx := sort(L, 'key'=(i->i[1]), 'output'='permutation');
out := Recurse(L, Lx, Ly, 1, numelems(L));
return sqrt(out[1]), out[2];
end proc; # ModuleApply
local
BruteForce := proc(L, Lx, r1:=1, r2:=numelems(L), $)
local d, p, n, i, j;
d := infinity;
for i from r1 to r2-1 do
for j from i+1 to r2 do
n := dist( L[Lx[i]], L[Lx[j]] );
if n < d then
d := n;
p := [ L[Lx[i]], L[Lx[j]] ];
end if;
end do; # j
end do; # i
return (d, p);
end proc; # BruteForce
local dist := (p, q)->(( (p[1]-q[1])^2+(p[2]-q[2])^2 ));
local Recurse := proc(L, Lx, Ly, r1, r2)
local m, xm, rDist, rPair, lDist, lPair, minDist, minPair, S, i, j, Lyr, Lyl;
if r2-r1 <= 3 then
return BruteForce(L, Lx, r1, r2);
end if;
m := ceil((r2-r1)/2)+r1;
xm := (L[Lx[m]][1] + L[Lx[m-1]][1])/2;
(Lyr, Lyl) := selectremove( i->L[i][1] < xm, Ly);
(rDist, rPair) := thisproc(L, Lx, Lyr, r1, m-1);
(lDist, lPair) := thisproc(L, Lx, Lyl, m, r2);
if rDist < lDist then
minDist := rDist;
minPair := rPair;
else
minDist := lDist;
minPair := lPair;
end if;
S := [ seq( `if`(abs(xm - L[i][1])^2< minDist, L[i], NULL ), i in Ly ) ];
for i from 1 to nops(S)-1 do
for j from i+1 to nops(S) do
if abs( S[i][2] - S[j][2] )^2 >= minDist then
break;
elif dist(S[i], S[j]) < minDist then
minDist := dist(S[i], S[j]);
minPair := [S[i], S[j]];
end if;
end do;
end do;
return (minDist, minPair);
end proc; #Recurse
end module; #ClosestPair</syntaxhighlight>
{{out}}<syntaxhighlight lang="maple">
> 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="mathematica">nearestPair[data_] :=
Block[{pos, dist = N[Outer[EuclideanDistance, data, data, 1]]},
pos = Position[dist, Min[DeleteCases[Flatten[dist], 0.]]];
data[[pos[[1]]]]]</
'''O(''n''<sup>2</sup>) output:'''
<
9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,
8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,
4.6268}, {1.45428, 0.087596}}]
{{7.46911, 4.71611}, {7.46489, 4.6268}}</
''' O(''n''log ''n'') '''
<syntaxhighlight lang="mathematica">closestPair[ptsIn_] :=
Module[{xP, yP,
pts},(*Top level function.Sorts the pts by x and by y and then \
calls closestPairR[]*)pts = N[ptsIn];
xP = Sort[pts, #1[[1]] < #2[[1]] &];
yP = Sort[pts, #1[[2]] < #2[[2]] &];
closestPairR[xP, yP]]
closestPairR[xP_, yP_] :=
Module[{n, mid, xL, xR, xm, yL, yR, dL, pairL, dmin, pairMin, yS, nS,
closest, closestP, k,
cDist},(*where xP is P(1).. P(n) sorted by x coordinate,
and yP is P(1).. P(n) sorted by y coordinate (ascending order)*)
n = Length[xP];
If[n <= 3,(*Brute Force*)
Piecewise[{{{\[Infinity], {}},
n < 2}, {{EuclideanDistance[xP[[1]], xP[[2]]], {xP[[1]],
xP[[2]]}},
n == 2}, {Last@
MinimalBy[{{EuclideanDistance[xP[[1]], xP[[2]]], {xP[[1]],
xP[[2]]}}, {EuclideanDistance[xP[[1]], xP[[3]]], {xP[[1]],
xP[[3]]}}, {EuclideanDistance[xP[[3]], xP[[2]]], {xP[[3]],
xP[[2]]}}}, First], n == 3}}], mid = Ceiling[n/2];
xL = xP[[1 ;; mid]];
xR = xP[[mid + 1 ;; n]];
xm = xP[[mid]];
yL = Select[yP, #[[1]] <= xm[[1]] &];
yR = Select[yP, #[[1]] > xm[[1]] &];
{dL, pairL} = closestPairR[xL, yL];
{dmin, pairMin} = closestPairR[xR, yR];
If[dL < dmin, {dmin, pairMin} = {dL, pairL}];
yS = Select[yP, Abs[#[[1]] - xm[[1]]] <= dmin &];
nS = Length[yS];
{closest, closestP} = {dmin, pairMin};
Table[k = i + 1;
While[(k <= nS) && (yS[[k, 2]] - yS[[i, 2]] < dmin),
cDist = EuclideanDistance[yS[[k]], yS[[i]]];
If[cDist <
closest, {closest, closestP} = {cDist, {yS[[k]], yS[[i]]}}];
k = k + 1], {i, 1, nS - 1}];
{closest, closestP}](*end if*)]
</syntaxhighlight>
''' O(''n''log''n'') output: '''
<syntaxhighlight lang="mathematica">closestPair[{{0.748501, 4.09624}, {3.00302, 5.26164}, {3.61878,
9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,
8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,
4.6268}, {1.45428, 0.087596}}]
{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.
<
N = numel(xP);
Line 2,366 ⟶ 2,700:
end %for
end %if (N <= 3)
end %closestPair</
{{out}}
<
distance =
Line 2,378 ⟶ 2,712:
pair =
[1x2 double] [1x2 double] %The pair is [1.5 2] and [2 2] which is correct</
=={{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
While s<>""
i=i+1
For j=1 To 2
k=Text.GetIndexOf(s,",")
ss=Text.GetSubText(s,1,k-1)
s=Text.GetSubTextToEnd(s,k+1)
pxy[i][j]=ss
EndFor
EndWhile
n=i
i=1
j=2
dd=Math.Power(pxy[i][1]-pxy[j][1],2)+Math.Power(pxy[i][2]-pxy[j][2],2)
ddmin=dd
ii=i
jj=j
For i=1 To n
For j=1 To n
dd=Math.Power(pxy[i][1]-pxy[j][1],2)+Math.Power(pxy[i][2]-pxy[j][2],2)
If dd>0 Then
If dd<ddmin Then
ddmin=dd
ii=i
jj=j
EndIf
EndIf
EndFor
EndFor
sqrt1=ddmin
sqrt2=ddmin/2
For i=1 To 20
If sqrt1=sqrt2 Then
Goto exitfor
EndIf
sqrt1=sqrt2
sqrt2=(sqrt1+(ddmin/sqrt1))/2
EndFor
exitfor:
TextWindow.WriteLine("the minimum distance "+sqrt2)
TextWindow.WriteLine("is between the points:")
TextWindow.WriteLine(" ["+pxy[ii][1]+","+pxy[ii][2]+"] and")
TextWindow.WriteLine(" ["+pxy[jj][1]+","+pxy[jj][2]+"]")</syntaxhighlight>
{{out}}
<pre>
the minimum distance 0,0779101913551750943201426138
is between the points:
[0.891663,0.888594] and
[0.925092,0.818220]
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math, algorithm
type
Point = tuple[x, y: float]
Pair = tuple[p1, p2: Point]
Result = tuple[minDist: float; minPoints: Pair]
#---------------------------------------------------------------------------------------------------
template sqr(x: float): float = x * x
#---------------------------------------------------------------------------------------------------
func dist(point1, point2: Point): float =
sqrt(sqr(point2.x - point1.x) + sqr(point2.y - point1.y))
#---------------------------------------------------------------------------------------------------
func bruteForceClosestPair*(points: openArray[Point]): Result =
doAssert(points.len >= 2, "At least two points required.")
result.minDist = Inf
for i in 0..<points.high:
for j in (i + 1)..points.high:
let d = dist(points[i], points[j])
if d < result.minDist:
result = (d, (points[i], points[j]))
#---------------------------------------------------------------------------------------------------
func closestPair(xP, yP: openArray[Point]): Result =
## Recursive function which takes two open arrays as arguments: the first
## sorted by increasing values of x, the second sorted by increasing values of y.
if xP.len <= 3:
return xP.bruteForceClosestPair()
let m = xP.high div 2
let xL = xP[0..m]
let xR = xP[(m + 1)..^1]
let xm = xP[m].x
var yL, yR: seq[Point]
for p in yP:
if p.x <= xm: yL.add(p)
else: yR.add(p)
let (dL, pairL) = closestPair(xL, yL)
let (dR, pairR) = closestPair(xR, yR)
let (dMin, pairMin) = if dL < dR: (dL, pairL) else: (dR, pairR)
var yS: seq[Point]
for p in yP:
if abs(xm - p.x) < dmin: yS.add(p)
result = (dMin, pairMin)
for i in 0..<yS.high:
var k = i + 1
while k < yS.len and ys[k].y - yS[i].y < dMin:
let d = dist(yS[i], yS[k])
if d < result.minDist:
result = (d, (yS[i], yS[k]))
inc k
#---------------------------------------------------------------------------------------------------
func closestPair*(points: openArray[Point]): Result =
let xP = points.sortedByIt(it.x)
let yP = points.sortedByIt(it.y)
doAssert(points.len >= 2, "At least two points required.")
result = closestPair(xP, yP)
#———————————————————————————————————————————————————————————————————————————————————————————————————
import random, times, strformat
randomize()
const N = 50_000
const Max = 10_000.0
var points: array[N, Point]
for pt in points.mitems: pt = (rand(Max), rand(Max))
echo "Sample contains ", N, " random points."
echo ""
let t0 = getTime()
echo "Brute force algorithm:"
echo points.bruteForceClosestPair()
let t1 = getTime()
echo "Optimized algorithm:"
echo points.closestPair()
let t2 = getTime()
echo ""
echo fmt"Execution time for brute force algorithm: {(t1 - t0).inMilliseconds:>4} ms"
echo fmt"Execution time for optimized algorithm: {(t2 - t1).inMilliseconds:>4} ms"</syntaxhighlight>
{{out}}
<pre>Sample contains 50000 random points.
Brute force algorithm:
(minDist: 0.1177082437919083, minPoints: (p1: (x: 3686.601318778875, y: 2187.261792916939), p2: (x: 3686.483703931143, y: 2187.257104820359)))
Optimized algorithm:
(minDist: 0.1177082437919083, minPoints: (p1: (x: 3686.483703931143, y: 2187.257104820359), p2: (x: 3686.601318778875, y: 2187.261792916939)))
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}}==
<
type point = { x : float; y : float }
Line 2,513 ⟶ 3,008:
Printf.printf "(%f, %f) (%f, %f) Dist %f\n" a.x a.y b.x b.y (dist c)
</syntaxhighlight>
=={{header|Oz}}==
Translation of pseudocode:
<
fun {Distance X1#Y1 X2#Y2}
{Sqrt {Pow X2-X1 2.0} + {Pow Y2-Y1 2.0}}
Line 2,615 ⟶ 3,109:
{ForAll Points RandomPoint}
{Show Points}
{Show {ClosestPair Points}}</
=={{header|PARI/GP}}==
Naive quadratic solution.
<
my(r=norml2(v[1]-v[2]),at=[1,2]);
for(a=1,#v-1,
Line 2,630 ⟶ 3,123:
);
[v[at[1]],v[at[2]]]
};</
=={{header|Pascal}}==
Brute force only calc square of distance, like AWK etc...
As fast as [[Closest-pair_problem#Faster_Brute-force_Version | D ]] .
<
{$IFDEF FPC}
{$MODE Delphi}
Line 2,700 ⟶ 3,193:
Writeln('P[',i:4,']= x: ',PointLst[i].ptX:0:8,
' y: ',PointLst[i].ptY:0:8);
end.</
//without randomize always same results
//32-Bit
Line 2,716 ⟶ 3,209:
//32-Bit
PointCnt = { 10000*sqrt(10) } 31623;-> real 0m1.112s 10x times runtime</pre>
=={{header|PascalABC.NET}}==
Brute forse algorithm.
<syntaxhighlight lang="delphi">
type Point = auto class
x,y: real;
function Distance(p: Point): real := Sqrt((x-p.x)**2 + (y-p.y)**2);
end;
function Pnt(x,y: real) := new Point(x,y);
function RandomPoint: Point := Pnt(RandomReal(0,10),RandomReal(0,10));
function ClosestPair(points: array of Point): (Point,Point);
begin
var pairs := points.Combinations(2);
var pair := pairs.MinBy(pair -> pair[0].Distance(pair[1]));
Result := (pair[0],pair[1]);
end;
begin
var points := ArrGen(10,i -> RandomPoint);
points.Println;
var ClPair := ClosestPair(points);
Println(ClPair,ClPair[0].Distance(ClPair[1]));
end.
</syntaxhighlight>
{{out}}
<pre>
(3.37,1.75) (3.87,9.48) (6.21,7.71) (7.52,7.95) (6.94,2.07) (1.72,5.92) (6.04,0.66) (3.46,0.93) (6.09,1.97) (4.95,0.19)
((3.37,1.75),(3.46,0.93)) 0.824924238945614
</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);
sub dist {
my ($a, $b) = @_;
return
}
sub closest_pair_simple {
my @points = @{ shift @_ };
my ($a, $b, $d) = ( $points[0], $points[1], dist($points[0], $points[1]) );
my $
($a, $b, $d) = ($p, $l, $t) if $t < $d;
}
}
sub closest_pair {
my @r = @{ shift @_ };
closest_pair_real( [sort { $a->[0] <=> $b->[0] } @r], [sort { $a->[1] <=> $b->[1] } @r] )
}
sub closest_pair_real {
my ($rx, $ry) = @_;
my(@yR,
my $N = @$rx;
my $midx = ceil($N/2)-1;
my @PL = @$rx[ 0 .. $midx];
my @
my
$_->[0] <= $xm ? push @yR, $_ : push @yL, $_ for @$ry;
my ($al, $bl, $dL) = closest_pair_real(\@PL, \@yR);
my ($ar, $br, $dR) = closest_pair_real(\@PR, \@yL);
my ($w1, $w2, $closest) = $dR > $dL ? ($al, $bl, $dL) : ($ar, $br, $dR);
abs($xm - $_->[0]) < $closest and push @yS, $_ for @$ry;
for my
while ( $k <= $#yS and ($yS[$k]->[1] - $yS[$i]->[1]) < $closest ) {
my
($w1, $w2, $closest) = ($yS[$k], $yS[$i], $d) if $d < $closest;
}
}
}
push @points, [rand(20)-10, rand(20)-10] for 1..5000;
printf "%.8f between (%.5f, %.5f), (%.5f, %.5f)\n", $_->[2], @{$$_[0]}, @{$$_[1]}
for [closest_pair_simple(\@points)], [closest_pair(\@points)];</syntaxhighlight>
{{out}}
<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="phix">(phixonline)-->
<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>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">mind</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">minp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x2</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mind</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y2</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mind</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mind</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span>
<span style="color: #000000;">minp</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mind</span><span style="color: #0000FF;">),</span><span style="color: #000000;">minp</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">testset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rnd</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">points</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (Sorting the final point pair makes brute/dc more likely to tally. Note however
-- when >1 equidistant pairs exist, brute and dc may well return different pairs;
-- it is only a problem if they decide to return different minimum distances.)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Closest pair: {%f,%f} {%f,%f}, distance=%f (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">X</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">byY</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">yP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"byY"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">distsq</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2</span>
<span style="color: #000000;">x1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">x2</span>
<span style="color: #000000;">y1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">y2</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- where xP is P(1) .. P(N) sorted by x coordinate, and
-- yP is P(1) .. P(N) sorted by y coordinate (ascending order)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">midN</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">N</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xL</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">xR</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">N</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">yL</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">yR</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">xm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]<=</span><span style="color: #000000;">xm</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">yL</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">yR</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yR</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dL</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairL</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yL</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dR</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairR</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xR</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yR</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dmin</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairMin</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">({</span><span style="color: #000000;">dL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairL</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">dR</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairR</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">yS</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xm</span><span style="color: #0000FF;">-</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">dmin</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">yS</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nS</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">closest</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">dmin</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairMin</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nS</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">nS</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">dmin</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">distsq</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">closest</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">closest</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">closest</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">points</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (see note above)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Closest pair: {%f,%f} {%f,%f}, distance=%f (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,023 ⟶ 3,418:
Closest pair: {0.0328051,0.0966250} {0.0328850,0.0966250}, distance=0.000120143 (0.14s)
</pre>
=={{header|PicoLisp}}==
<
(let Min T
(use (Pt1 Pt2)
Line 3,038 ⟶ 3,432:
Min )
(setq Min N Pt1 P Pt2 Q) ) ) )
(list Pt1 Pt2 (sqrt Min)) ) ) )</
Test:
<pre>: (scl 6)
Line 3,056 ⟶ 3,450:
(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,091 ⟶ 3,484:
end;
end closest;
</syntaxhighlight>
=={{header|Prolog}}==
'''Brute force version, works with SWI-Prolog, tested on version 7.2.3.
<syntaxhighlight lang="prolog">
% main predicate, find and print closest point
do_find_closest_points(Points) :-
points_closest(Points, points(point(X1,Y1),point(X2,Y2),Dist)),
format('Point 1 : (~p, ~p)~n', [X1,Y1]),
format('Point 1 : (~p, ~p)~n', [X2,Y2]),
format('Distance: ~p~n', [Dist]).
% Find the distance between two points
distance(point(X1,Y1), point(X2,Y2), points(point(X1,Y1),point(X2,Y2),Dist)) :-
Dx is X2 - X1,
Dy is Y2 - Y1,
Dist is sqrt(Dx * Dx + Dy * Dy).
% find the closest point that relatest to another point
point_closest(Points, Point, Closest) :-
select(Point, Points, Remaining),
maplist(distance(Point), Remaining, PointList),
foldl(closest, PointList, 0, Closest).
% find the closest point/dist pair for all points
points_closest(Points, Closest) :-
maplist(point_closest(Points), Points, ClosestPerPoint),
foldl(closest, ClosestPerPoint, 0, Closest).
% used by foldl to get the lowest point/distance combination
closest(points(P1,P2,Dist), 0, points(P1,P2,Dist)).
closest(points(_,_,Dist), points(P1,P2,Dist2), points(P1,P2,Dist2)) :-
Dist2 < Dist.
closest(points(P1,P2,Dist), points(_,_,Dist2), points(P1,P2,Dist)) :-
Dist =< Dist2.
</syntaxhighlight>
To test, pass in a list of points.
<syntaxhighlight lang="prolog">do_find_closest_points([
point(0.654682, 0.925557),
point(0.409382, 0.619391),
point(0.891663, 0.888594),
point(0.716629, 0.996200),
point(0.477721, 0.946355),
point(0.925092, 0.818220),
point(0.624291, 0.142924),
point(0.211332, 0.221507),
point(0.293786, 0.691701),
point(0.839186, 0.728260)
]).
</syntaxhighlight>
{{out}}
<pre>
Point 1 : (0.925092, 0.81822)
Point 1 : (0.891663, 0.888594)
Distance: 0.07791019135517516
true ;
false.
</pre>
=={{header|PureBasic}}==
'''Brute force version
<
Protected N=ArraySize(P()), i, j
Protected mindistance.f=Infinity(), t.d
Line 3,114 ⟶ 3,562:
ProcedureReturn mindistance
EndProcedure
</syntaxhighlight>
Implementation can be as
<
x.d
y.d
Line 3,145 ⟶ 3,593:
Data.d 0.716629, 0.996200, 0.477721, 0.946355, 0.925092, 0.818220
Data.d 0.624291, 0.142924, 0.211332, 0.221507, 0.293786, 0.691701, 0.839186, 0.72826
EndDataSection</
{{out}}
<pre>Mindistance= 0.077910
Line 3,152 ⟶ 3,600:
Press ENTER to quit</pre>
=={{header|Python}}==
<
Compute nearest pair of points using two algorithms
Line 3,240 ⟶ 3,687:
times()
times()
times()</
{{out}} followed by timing comparisons<br>
Line 3,296 ⟶ 3,743:
Time for closestPair 0.119326618327
>>> </pre></div>
=={{header|R}}==
{{works with|R|2.8.1+}}
Brute force solution as per wikipedia pseudo-code
<
xy = cbind(x,y)
cp = bruteforce(xy)
Line 3,329 ⟶ 3,775:
else bruteforce(pmatrix,n+1,pd)
}
}</
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.
<
{
distancev <- function(pointsv)
Line 3,351 ⟶ 3,797:
"\n\tDistance: ",minrow[3],"\n",sep="")
c(distance=minrow[3],x1.x=x[minrow[1]],y1.y=y[minrow[1]],x2.x=x[minrow[2]],y2.y=y[minrow[2]])
}</
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.
<
# 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,373 ⟶ 3,819:
x2=x[point.pair[2],1],y2=x[point.pair[2],2],
distance=min.dist)
}</
Example<
y = (sample(-1000.00:1000.00,length(x)))
cp = closest.pairs(x,y)
Line 3,412 ⟶ 3,858:
0.17 0.00 0.19
</syntaxhighlight>
Using dist function for brute force, but divide and conquer (as per pseudocode) for speed:
<
{
if (!is.null(y))
Line 3,503 ⟶ 3,949:
print(closest.pairs.bruteforce(x,y))
cat(sprintf("That took %.2f seconds.\n",proc.time()[3] - tstart))
</syntaxhighlight>
{{out}}
<pre>
Line 3,537 ⟶ 3,983:
That took 6.38 seconds.
</pre>
=={{header|Racket}}==
The brute force solution using complex numbers
to represent pairs.
<
#lang racket
(define (dist z0 z1) (magnitude (- z1 z0)))
Line 3,557 ⟶ 4,002:
(displayln (~a "Closest points: " result))
(displayln (~a "Distance: " (dist* result)))
</syntaxhighlight>
The divide and conquer algorithm using a struct to represent points
<
#lang racket
(struct point (x y) #:transparent)
Line 3,658 ⟶ 4,103:
(match-define (list (point p1x p1y) (point p2x p2y)) (closest-pair points))
(printf "Closest points on a quadratic curve (~a,~a) (~a,~a)\n" p1x p1y p2x p2y)
</syntaxhighlight>
{{out}}
<
Closest points: (0+1i 1+2i)
Distance: 1.4142135623730951
Closest points on a quadratic curve (0,0) (1,1)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl 5}}
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] }
my @candidates = @points.sort(*.[0]).rotor( 10 => -2, :partial).race.map: { closest-pair-simple(@$_) }
say 'simple ' ~ (@candidates.sort: *.[2]).head(1).gist;
@candidates = @points.sort(*.[0]).rotor( 10 => -2, :partial).race.map: { closest-pair(@$_) }
say 'real ' ~ (@candidates.sort: *.[2]).head(1).gist;
}
sub dist-squared(@a, @b) { (@a[0] - @b[0])² + (@a[1] - @b[1])² }
sub closest-pair-simple(@points is copy) {
return ∞ if @points < 2;
my ($a, $b, $d) = |@points[0,1], dist-squared(|@points[0,1]);
while @points {
my \p = pop @points;
for @points -> \l {
($a, $b, $d) = p, l, $_ if $_ < $d given dist-squared(p, l);
}
}
$a, $b, $d.sqrt
}
sub closest-pair(@r) {
closest-pair-real (@r.sort: *.[0]), (@r.sort: *.[1])
}
sub closest-pair-real(@rx, @ry) {
return closest-pair-simple(@rx) if @rx ≤ 3;
my \N = @rx;
my \midx = ceiling(N/2) - 1;
my @PL := @rx[ 0 .. midx];
my @PR := @rx[midx+1 ..^ N ];
my \xm = @rx[midx;0];
(.[0] ≤ xm ?? my @yR !! my @yL).push: @$_ for @ry;
my (\al, \bl, \dL) = closest-pair-real(@PL, @yR);
my (\ar, \br, \dR) = closest-pair-real(@PR, @yL);
my ($w1, $w2, $closest) = dR < dL ?? (ar, br, dR) !! (al, bl, dL);
my @yS = @ry.grep: { (xm - .[0]).abs < $closest }
for 0 ..^ @yS -> \i {
for i+1 ..^ @yS -> \k {
next unless @yS[k;1] - @yS[i;1] < $closest;
($w1, $w2, $closest) = |@yS[k, i], $_ if $_ < $closest given dist-squared(|@yS[k, i]).sqrt;
}
}
$w1, $w2, $closest
}</syntaxhighlight>
{{out}}
<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).
<
parse arg N
if
if
if
if datatype(seed, 'W') then call random ,,seed /*seed for RANDOM (BIF) repeatability.*/
w= length(
/*╔══════════════════════╗*/ do j=1 for N /*generate N random points*/
/*║ generate N points. ║*/ @x.j= random(
/*╚══════════════════════╝*/ @y.j= random(
end /*j*/ /*X & Y make the point.*/
/* [↓] use of XJ & YJ speed things up.*/
do j=1 for N-1;
do k=j+1
if
end /*k*/ /* [↑] needn't take SQRT of
end /*j*/ /* [↑] when done, A & B are the points*/
$= 'For ' N " points, the minimum distance between the two points: "
say $ center("x", w, '═')" "
say left('', length($) - 1)
say left('', length($) - 1)
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); m.=9; numeric form; h=d+6
numeric digits; parse value format(x,2,1,,0) 'E0'
do j=0 while h>9; m.j= h;
do k=j+5 to 0 by -1; numeric digits m.k; g= (g+x/g)*.5; end /*k*/;
{{out|output|text= when using the default input of: <tt> 100 </tt>}}
<pre>
For 100 points, the minimum distance between the two points: ══x══ ══y══ is: 219.228192
Line 3,707 ⟶ 4,210:
[ 7483, 1700]
</pre>
{{out|output|text= when using the input of: <tt> 200 </tt>}}
<pre>
For 200 points, the minimum distance between the two points: ══x══ ══y══ is: 39.408121
Line 3,713 ⟶ 4,216:
[17627, 19198]
</pre>
{{out|output|text= when using the input of: <tt> 1000 </tt>
}}
<pre>
Line 3,720 ⟶ 4,223:
[ 6263, 19108]
</pre>
=={{header|Ring}}==
<
decimals(10)
x = list(10)
Line 3,755 ⟶ 4,257:
next
see "closest pair is : " + mini + " and " + minj + " at distance " + sqrt(min)
</syntaxhighlight>
Output:
<pre>
closest pair is : 3 and 6 at distance 0.0779101914
</pre>
=={{header|RPL}}==
Brute-force approach, because it's unlikely that anyone would use a RPL calculator to process a large set of points.
« → points
« 0 0 0
1 points SIZE 1 - '''FOR''' j
j 1 + points SIZE '''FOR''' k
points j GET points k GET - ABS
'''IF''' DUP2 < '''THEN''' 4 ROLLD 3 DROPN j k ROT '''ELSE''' DROP '''END'''
'''NEXT NEXT''' ROT ROT
points SWAP GET points ROT GET
'''IF''' DUP2 RE SWAP RE < '''THEN''' SWAP '''END''' <span style="color:grey">@ sort by ascending x</span>
2 →LIST
» » '<span style="color:blue">CLOSEPR</span>' STO
{ (0,0) (1,0) (1,2) (3,4) (5,5) (7,5) (3,5) } <span style="color:blue">CLOSEPR</span>
{{out}}
<pre>
2: 8.60232526704
1: { (0,0) (7,5) }
</pre>
=={{header|Ruby}}==
<
def distance(p1, p2)
Line 3,814 ⟶ 4,336:
x.report("bruteforce") {ans1 = closest_bruteforce(points)}
x.report("recursive") {ans2 = closest_recursive(points)}
end</
'''Sample output'''
<pre>
Line 3,826 ⟶ 4,348:
=={{header|Run BASIC}}==
Courtesy http://dkokenge.com/rbp
<
dim x(n)
dim y(n)
Line 3,866 ⟶ 4,388:
data 0.211332, 0.221507
data 0.293786, 0.691701
data 0.839186, 0.72826</
=={{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
//! algorithm, since it's (arguably) easier to implement, and an efficient implementation does not
//! require use of unsafe.
//!
//! [algorithm]: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
extern crate num;
use num::complex::Complex;
use std::cmp::{Ordering, PartialOrd};
use std::collections::BTreeSet;
type Point = Complex<f32>;
/// Wrapper around `Point` (i.e. `Complex<f32>`) so that we can use a `TreeSet`
#[derive(PartialEq)]
struct YSortedPoint {
point: Point,
}
impl PartialOrd for YSortedPoint {
fn partial_cmp(&self, other: &YSortedPoint) -> Option<Ordering> {
(self.point.im, self.point.re).partial_cmp(&(other.point.im, other.point.re))
}
}
impl Ord for YSortedPoint {
fn cmp(&self, other: &YSortedPoint) -> Ordering {
self.partial_cmp(other).unwrap()
}
}
impl Eq for YSortedPoint {}
fn closest_pair(points: &mut [Point]) -> Option<(Point, Point)> {
if points.len() < 2 {
return None;
}
points.sort_by(|a, b| (a.re, a.im).partial_cmp(&(b.re, b.im)).unwrap());
let mut closest_pair = (points[0], points[1]);
let mut closest_distance_sqr = (points[0] - points[1]).norm_sqr();
let mut closest_distance = closest_distance_sqr.sqrt();
// the strip that we inspect for closest pairs as we sweep right
let mut strip: BTreeSet<YSortedPoint> = BTreeSet::new();
strip.insert(YSortedPoint { point: points[0] });
strip.insert(YSortedPoint { point: points[1] });
// index of the leftmost point on the strip (on points)
let mut leftmost_idx = 0;
// Start the sweep!
for (idx, point) in points.iter().enumerate().skip(2) {
// Remove all points farther than `closest_distance` away from `point`
// along the x-axis
while leftmost_idx < idx {
let leftmost_point = &points[leftmost_idx];
if (leftmost_point.re - point.re).powi(2) < closest_distance_sqr {
break;
}
strip.remove(&YSortedPoint {
point: *leftmost_point,
});
leftmost_idx += 1;
}
// Compare to points in bounding box
{
let low_bound = YSortedPoint {
point: Point {
re: ::std::f32::INFINITY,
im: point.im - closest_distance,
},
};
let mut strip_iter = strip.iter().skip_while(|&p| p < &low_bound);
loop {
let point2 = match strip_iter.next() {
None => break,
Some(p) => p.point,
};
if point2.im - point.im >= closest_distance {
// we've reached the end of the box
break;
}
let dist_sqr = (*point - point2).norm_sqr();
if dist_sqr < closest_distance_sqr {
closest_pair = (point2, *point);
closest_distance_sqr = dist_sqr;
closest_distance = dist_sqr.sqrt();
}
}
}
// Insert point into strip
strip.insert(YSortedPoint { point: *point });
}
Some(closest_pair)
}
pub fn main() {
let mut test_data = [
Complex::new(0.654682, 0.925557),
Complex::new(0.409382, 0.619391),
Complex::new(0.891663, 0.888594),
Complex::new(0.716629, 0.996200),
Complex::new(0.477721, 0.946355),
Complex::new(0.925092, 0.818220),
Complex::new(0.624291, 0.142924),
Complex::new(0.211332, 0.221507),
Complex::new(0.293786, 0.691701),
Complex::new(0.839186, 0.728260),
];
let (p1, p2) = closest_pair(&mut test_data[..]).unwrap();
println!("Closest pair: {} and {}", p1, p2);
println!("Distance: {}", (p1 - p2).norm_sqr().sqrt());
}
</syntaxhighlight>
{{out}}
<pre>
Closest pair: 0.891663+0.888594i and 0.925092+0.81822i
Distance: 0.07791013
</pre>
=={{header|Scala}}==
<
import scala.util.Random
Line 4,002 ⟶ 4,649:
}
}
</syntaxhighlight>
{{out}}
Line 4,010 ⟶ 4,657:
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:
<
var float: x is 0.0;
var float: y is 0.0;
Line 4,046 ⟶ 4,692:
result := [] (points[savei], points[savej]);
end if;
end func;</
=={{header|Sidef}}==
{{trans|
<
sqr(a[0] - b[0]) + sqr(a[1] - b[1])
}
Line 4,120 ⟶ 4,765:
var points = N.of { [1.rand*20 - 10, 1.rand*20 - 10] }
var (af, bf, df) = closest_pair(points)
say "#{df} at (#{af.join(' ')}), (#{bf.join(' ')})"</
=={{header|Smalltalk}}==
See [[Closest-pair problem/Smalltalk]]
=={{header|Swift}}==
<syntaxhighlight lang="swift">import Foundation
struct Point {
var x: Double
var y: Double
func distance(to p: Point) -> Double {
let x = pow(p.x - self.x, 2)
let y = pow(p.y - self.y, 2)
return (x + y).squareRoot()
}
}
extension Collection where Element == Point {
func closestPair() -> (Point, Point)? {
let (xP, xY) = (sorted(by: { $0.x < $1.x }), sorted(by: { $0.y < $1.y }))
return Self.closestPair(xP, xY)?.1
}
static func closestPair(_ xP: [Element], _ yP: [Element]) -> (Double, (Point, Point))? {
guard xP.count > 3 else { return xP.closestPairBruteForce() }
let half = xP.count / 2
let xl = Array(xP[..<half])
let xr = Array(xP[half...])
let xm = xl.last!.x
let (yl, yr) = yP.reduce(into: ([Element](), [Element]()), {cur, el in
if el.x > xm {
cur.1.append(el)
} else {
cur.0.append(el)
}
})
guard let (distanceL, pairL) = closestPair(xl, yl) else { return nil }
guard let (distanceR, pairR) = closestPair(xr, yr) else { return nil }
let (dMin, pairMin) = distanceL > distanceR ? (distanceR, pairR) : (distanceL, pairL)
let ys = yP.filter({ abs(xm - $0.x) < dMin })
var (closest, pairClosest) = (dMin, pairMin)
for i in 0..<ys.count {
let p1 = ys[i]
for k in i+1..<ys.count {
let p2 = ys[k]
guard abs(p2.y - p1.y) < dMin else { break }
let distance = abs(p1.distance(to: p2))
if distance < closest {
(closest, pairClosest) = (distance, (p1, p2))
}
}
}
return (closest, pairClosest)
}
func closestPairBruteForce() -> (Double, (Point, Point))? {
guard count >= 2 else { return nil }
var closestPoints = (self.first!, self[index(after: startIndex)])
var minDistance = abs(closestPoints.0.distance(to: closestPoints.1))
guard count != 2 else { return (minDistance, closestPoints) }
for i in 0..<count {
for j in i+1..<count {
let (iIndex, jIndex) = (index(startIndex, offsetBy: i), index(startIndex, offsetBy: j))
let (p1, p2) = (self[iIndex], self[jIndex])
let distance = abs(p1.distance(to: p2))
if distance < minDistance {
minDistance = distance
closestPoints = (p1, p2)
}
}
}
return (minDistance, closestPoints)
}
}
var points = [Point]()
for _ in 0..<10_000 {
points.append(Point(
x: .random(in: -10.0...10.0),
y: .random(in: -10.0...10.0)
))
}
print(points.closestPair()!)</syntaxhighlight>
{{out}}
<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''.
<
# retrieve the x-coordinate
Line 4,216 ⟶ 4,965:
set time [time {set ::dist($method) [closest_$method $points]} 1]
puts [format "%-10s %9d %9d %s" $method $::comparisons [lindex $time 0] [lindex $::dist($method) 0]]
}</
{{out}}
<pre>method compares time closest
Line 4,222 ⟶ 4,971:
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,232 ⟶ 4,980:
each remaining pair the sum of the squares of the differences
between corresponding coordinates.
<
clop = @iiK0 fleq$-&l+ *EZF ^\~& plus+ sqr~~+ minus~~bbI</
The divide and conquer algorithm following the specification
given above is a little more hairy but not much longer.
The <code>eudist</code> library function
is used to compute the distance between points.
<
#import flo
Line 4,246 ⟶ 4,994:
^(fleq-<&l,fleq-<&r); @blrNCCS ~&lrbhthPX2X+ ~&a^& fleq$-&l+ leql/8?al\^(eudist,~&)*altK33htDSL -+
^C/~&rr ^(eudist,~&)*tK33htDSL+ @rlrlPXPlX ~| fleq^\~&lr abs+ minus@llPrhPX,
^/~&ar @farlK30K31XPGbrlrjX3J ^/~&arlhh @W lesser fleq@bl+-</
test program:
<
<
Line 4,270 ⟶ 5,018:
#cast %eeWWA
example = clop test_data</
{{out}}
The output shows the minimum distance and the two points separated
Line 4,280 ⟶ 5,028:
(-1.745694e+00,3.276434e+00))
</pre>
=={{header|VBA}}==
<
Private Type MyPoint
Line 4,335 ⟶ 5,082:
Dist = Sqr((p1.X - p2.X) ^ 2 + (p1.Y - p2.Y) ^ 2)
End Function
</syntaxhighlight>
{{out}}
<pre>For 10 points, runtime : 0 sec.
Line 4,357 ⟶ 5,104:
dist : 2,445694
--------------------------------------------------</pre>
=={{header|Visual FoxPro}}==
<
CLOSE DATABASES ALL
CREATE CURSOR pairs(id I, xcoord B(6), ycoord B(6))
Line 4,380 ⟶ 5,126:
? "Closest pair is " + TRANSFORM(id1) + " and " + TRANSFORM(id2) + "."
? "Distance is " + TRANSFORM(SQRT(dist2))
</syntaxhighlight>
{{out}}
<pre>
Line 4,387 ⟶ 5,133:
Closest pair is 3 and 6.
Distance is 0.077910.
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">import "./math" for Math
import "./sort" for Sort
var distance = Fn.new { |p1, p2| Math.hypot(p1[0] - p2[0], p1[1] - p2[1]) }
var bruteForceClosestPair = Fn.new { |p|
var n = p.count
if (n < 2) Fiber.abort("There must be at least two points.")
var minPoints = [p[0], p[1]]
var minDistance = distance.call(p[0], p[1])
for (i in 0...n-1) {
for (j in i+1...n) {
var dist = distance.call(p[i], p[j])
if (dist < minDistance) {
minDistance = dist
minPoints = [p[i], p[j]]
}
}
}
return [minDistance, minPoints]
}
var optimizedClosestPair // recursive so pre-declare
optimizedClosestPair = Fn.new { |xP, yP|
var n = xP.count
if (n <= 3) return bruteForceClosestPair.call(xP)
var hn = (n/2).floor
var xL = xP.take(hn).toList
var xR = xP.skip(hn).toList
var xm = xP[hn-1][0]
var yL = yP.where { |p| p[0] <= xm }.toList
var yR = yP.where { |p| p[0] > xm }.toList
var ll = optimizedClosestPair.call(xL, yL)
var dL = ll[0]
var pairL = ll[1]
var rr = optimizedClosestPair.call(xR, yR)
var dR = rr[0]
var pairR = rr[1]
var dmin = dR
var pairMin = pairR
if (dL < dR) {
dmin = dL
pairMin = pairL
}
var yS = yP.where { |p| (xm - p[0]).abs < dmin }.toList
var nS = yS.count
var closest = dmin
var closestPair = pairMin
for (i in 0...nS-1) {
var k = i + 1
while (k < nS && (yS[k][1] - yS[i][1] < dmin)) {
var dist = distance.call(yS[k], yS[i])
if (dist < closest) {
closest = dist
closestPair = [yS[k], yS[i]]
}
k = k + 1
}
}
return [closest, closestPair]
}
var points = [
[ [5, 9], [9, 3], [2, 0], [8, 4], [7, 4], [9, 10], [1, 9], [8, 2], [0, 10], [9, 6] ],
[
[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]
]
]
for (p in points) {
var dp = bruteForceClosestPair.call(p)
var dist = dp[0]
var pair = dp[1]
System.print("Closest pair (brute force) is %(pair[0]) and %(pair[1]), distance %(dist)")
var xP = Sort.merge(p) { |x, y| (x[0] - y[0]).sign }
var yP = Sort.merge(p) { |x, y| (x[1] - y[1]).sign }
dp = optimizedClosestPair.call(xP, yP)
dist = dp[0]
pair = dp[1]
System.print("Closest pair (optimized) is %(pair[0]) and %(pair[1]), distance %(dist)\n")
}</syntaxhighlight>
{{out}}
<pre>
Closest pair (brute force) is [8, 4] and [7, 4], distance 1
Closest pair (optimized) is [7, 4] and [8, 4], distance 1
Closest pair (brute force) is [0.891663, 0.888594] and [0.925092, 0.81822], distance 0.077910191355175
Closest pair (optimized) is [0.891663, 0.888594] and [0.925092, 0.81822], distance 0.077910191355175
</pre>
Line 4,393 ⟶ 5,237:
and is perfectly adequate, even for a thousand points.
<
proc ClosestPair(P, N); \Show closest pair of points in array P
Line 4,429 ⟶ 5,273:
[0.839186, 0.728260]]; \9
ClosestPair(Data, 10);
]</
{{out}}
Line 4,436 ⟶ 5,280:
0.891663,0.888594 -- 0.925092,0.818220
</pre>
=={{header|Yabasic}}==
'''Versión de fuerza bruta:
<syntaxhighlight lang="yabasic">
minDist = 1^30
dim x(9), y(9)
x(0) = 0.654682 : y(0) = 0.925557
x(1) = 0.409382 : y(1) = 0.619391
x(2) = 0.891663 : y(2) = 0.888594
x(3) = 0.716629 : y(3) = 0.996200
x(4) = 0.477721 : y(4) = 0.946355
x(5) = 0.925092 : y(5) = 0.818220
x(6) = 0.624291 : y(6) = 0.142924
x(7) = 0.211332 : y(7) = 0.221507
x(8) = 0.293786 : y(8) = 0.691701
x(9) = 0.839186 : y(9) = 0.728260
for i = 0 to 8
for j = i+1 to 9
dist = (x(i) - x(j))^2 + (y(i) - y(j))^2
if dist < minDist then
minDist = dist
mini = i
minj = j
end if
next j
next i
print "El par mas cercano es ", mini, " y ", minj, " a una distancia de ", sqr(minDist)
end
</syntaxhighlight>
{{out}}
<pre>
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.
<
fcn init(_x,_y){ var[const] x=_x, y=_y; }
fcn distance(p){ (p.x-x).hypot(p.y-y) }
Line 4,453 ⟶ 5,329:
if(d1 < d2) p1 else p2
});
}</
<
2.0, 0.0, 8.0, 4.0,
7.0, 4.0, 9.0, 10.0,
Line 4,468 ⟶ 5,344:
0.293786, 0.691701, 0.839186, 0.72826)
.pump(List,Void.Read,Point);
closestPoints(points).println();</
{{out}}
<pre>
Line 4,474 ⟶ 5,350:
L(Point(0.925092,0.81822),Point(0.891663,0.888594),0.0779102)
</pre>
=={{header|ZX Spectrum Basic}}==
{{trans|BBC_BASIC}}
<
20 FOR i=1 TO 10
30 READ x(i),y(i)
Line 4,499 ⟶ 5,374:
210 DATA 0.211332,0.221507
220 DATA 0.293786,0.691701
230 DATA 0.839186,0.728260</
|