Closest-pair problem: Difference between revisions

Content added Content deleted

Inline

@@ Line 287: / Line 287: @@
       closestPair: Tuple!(double,cdouble,cdouble)(0.0947756, 643.407+788.387i, 643.463+788.31i)</pre>
 Time gave 0:06.28 elapsed for brute force, and 0:00.07 elapsed for the divide & conquer one (10_000 points).
+A faster brute-force version:
+<lang d>import std.stdio, std.typecons, std.math, std.random;
+auto bruteForceClosestPair2(cdouble[] points) {
+  auto minD = typeof(points[0].re).infinity;
+  size_t minI, minJ;
+  foreach (i; 0 .. points.length-1)
+    foreach (j; i+1 .. points.length) {
+      auto dre = points[i].re - points[j].re;
+      auto dim = points[i].im - points[j].im;
+      auto dist = dre * dre + dim * dim;
+      if (dist < minD) {
+        minD = dist;
+        minI = i;
+        minJ = j;
+      }
+    }
+  return tuple(sqrt(minD), points[minI], points[minJ]);
+}
+void main() {
+  auto rnd = Random(1);
+  auto points = new cdouble[10_000];
+  foreach (ref p; points)
+    p = uniform(0.0, 1000.0, rnd) + uniform(0.0, 1000.0, rnd) * 1i;
+  writeln("bruteForceClosestPair2: ", bruteForceClosestPair2(points));
+}</lang>
+Time gave 0:01.08 elapsed for brute-force version 2 (10_000 points).
 =={{header|F Sharp|F#}}==