From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 geometry/closestPair.cpp | 39 ++++++++++++++++++++++-----------------
 1 file changed, 22 insertions(+), 17 deletions(-)

(limited to 'geometry/closestPair.cpp')

diff --git a/geometry/closestPair.cpp b/geometry/closestPair.cpp
index cac544b..a7662b6 100644
--- a/geometry/closestPair.cpp
+++ b/geometry/closestPair.cpp
@@ -1,35 +1,40 @@
 double squaredDist(pt a, pt b) {
-	return (a.fst-b.fst) * (a.fst-b.fst) + (a.snd-b.snd) * (a.snd-b.snd);
+	return real(conj(a-b) * (a-b));
 }
 
 bool compY(pt a, pt b) {
-	if (a.snd == b.snd) return a.fst < b.fst;
-	return a.snd < b.snd;
+	return (imag(a) == imag(b)) ? real(a) < real(b) 
+															: imag(a) < imag(b);
 }
 
-// points.size() > 1 und alle Punkte müssen verschieden sein!
-double shortestDist(vector<pt> &points) {
+bool compX(pt a, pt b) {
+	return (real(a) == real(b)) ? imag(a) < imag(b)
+															: real(a) < real(b);
+}
+
+double shortestDist(vector<pt>& points) { // points.size() > 1
 	set<pt, bool(*)(pt, pt)> status(compY);
-	sort(points.begin(), points.end());
-	double opt = 1e30, sqrtOpt = 1e15;
+	sort(points.begin(), points.end(), compX);
+	double opt = 1.0/0.0, sqrtOpt = 1.0/0.0;
 	auto left = points.begin(), right = points.begin();
 	status.insert(*right); right++;
-	
+
 	while (right != points.end()) {
-		if (fabs(left->fst - right->fst) >= sqrtOpt) {
-			status.erase(*(left++));
+		if (left != right &&
+				abs(real(*left - *right)) >= sqrtOpt) {
+			status.erase(*left);
+			left++;
 		} else {
-			auto lower = status.lower_bound(pt(-1e20, right->snd - sqrtOpt));
-			auto upper = status.upper_bound(pt(-1e20, right->snd + sqrtOpt));
-			while (lower != upper) {
+			auto lower = status.lower_bound({-1.0/0.0, imag(*right) - sqrtOpt});
+			auto upper = status.upper_bound({-1.0/0.0, imag(*right) + sqrtOpt});
+			for (;lower != upper; lower++) {
 				double cand = squaredDist(*right, *lower);
 				if (cand < opt) {
 					opt = cand;
 					sqrtOpt = sqrt(opt);
-				}
-				++lower;
-			}
-			status.insert(*(right++));
+			}}
+			status.insert(*right);
+			right++;
 	}}
 	return sqrtOpt;
 }
-- 
cgit v1.2.3