Anonymous user
Closest-pair problem: Difference between revisions
no edit summary
No edit summary |
|||
Line 4,276:
(-1.745694e+00,3.276434e+00))
</pre>
=={{header|VBA}}==
<lang vb>Option Explicit
Private Type MyPoint
X As Single
Y As Single
End Type
Private Type MyPair
p1 As MyPoint
p2 As MyPoint
End Type
Sub Main()
Dim points() As MyPoint, i As Long, BF As MyPair, d As Single, Nb As Long
Dim T#
Randomize Timer
Nb = 10
Do
ReDim points(1 To Nb)
For i = 1 To Nb
points(i).X = Rnd * Nb
points(i).Y = Rnd * Nb
Next
d = 1000000000000#
T = Timer
BF = BruteForce(points, d)
Debug.Print "For " & Nb & " points, runtime : " & Timer - T & " sec."
Debug.Print "point 1 : X:" & BF.p1.X & " Y:" & BF.p1.Y
Debug.Print "point 2 : X:" & BF.p2.X & " Y:" & BF.p2.Y
Debug.Print "dist : " & d
Debug.Print "--------------------------------------------------"
Nb = Nb * 10
Loop While Nb <= 10000
End Sub
Private Function BruteForce(p() As MyPoint, mindist As Single) As MyPair
Dim i As Long, j As Long, d As Single, ClosestPair As MyPair
For i = 1 To UBound(p) - 1
For j = i + 1 To UBound(p)
d = Dist(p(i), p(j))
If d < mindist Then
mindist = d
ClosestPair.p1 = p(i)
ClosestPair.p2 = p(j)
End If
Next
Next
BruteForce = ClosestPair
End Function
Private Function Dist(p1 As MyPoint, p2 As MyPoint) As Single
Dist = Sqr((p1.X - p2.X) ^ 2 + (p1.Y - p2.Y) ^ 2)
End Function
</lang>
{{out}}
<pre>For 10 points, runtime : 0 sec.
point 1 : X:3,393822 Y:4,501572
point 2 : X:3,864069 Y:4,780283
dist : 0,5466374
--------------------------------------------------
For 100 points, runtime : 0 sec.
point 1 : X:79,85106 Y:26,7108
point 2 : X:80,3304 Y:27,44563
dist : 0,8773483
--------------------------------------------------
For 1000 points, runtime : 0,453125 sec.
point 1 : X:570,1923 Y:597,4487
point 2 : X:570,5159 Y:597,8205
dist : 0,4929211
--------------------------------------------------
For 10000 points, runtime : 44,69921875 sec.
point 1 : X:9759,147 Y:9084,795For 10 points, runtime : 0 sec.
point 1 : X:8,837788 Y:9,606443
point 2 : X:8,768814 Y:9,829233
dist : 0,2332223
--------------------------------------------------</pre>
=={{header|Visual FoxPro}}==
| |||