From 3f894510900184c928749654938d2a917bd4ad27 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Thu, 6 Oct 2016 23:03:04 +0200
Subject: Typesetting closest pair.

---
 geometry/closestPair.cpp | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)

(limited to 'geometry/closestPair.cpp')

diff --git a/geometry/closestPair.cpp b/geometry/closestPair.cpp
index 92b4551..cac544b 100644
--- a/geometry/closestPair.cpp
+++ b/geometry/closestPair.cpp
@@ -1,26 +1,26 @@
-double squaredDist(point a, point b) {
-	return (a.first-b.first) * (a.first-b.first) + (a.second-b.second) * (a.second-b.second);
+double squaredDist(pt a, pt b) {
+	return (a.fst-b.fst) * (a.fst-b.fst) + (a.snd-b.snd) * (a.snd-b.snd);
 }
 
-bool compY(point a, point b) {
-	if (a.second == b.second) return a.first < b.first;
-	return a.second < b.second;
+bool compY(pt a, pt b) {
+	if (a.snd == b.snd) return a.fst < b.fst;
+	return a.snd < b.snd;
 }
 
-double shortestDist(vector<point> &points) {
-	//check that points.size() > 1 and that ALL POINTS ARE DIFFERENT
-	set<point, bool(*)(point, point)> status(compY);
+// points.size() > 1 und alle Punkte müssen verschieden sein!
+double shortestDist(vector<pt> &points) {
+	set<pt, bool(*)(pt, pt)> status(compY);
 	sort(points.begin(), points.end());
 	double opt = 1e30, sqrtOpt = 1e15;
 	auto left = points.begin(), right = points.begin();
 	status.insert(*right); right++;
 	
 	while (right != points.end()) {
-		if (fabs(left->first - right->first) >= sqrtOpt) {
+		if (fabs(left->fst - right->fst) >= sqrtOpt) {
 			status.erase(*(left++));
 		} else {
-			auto lower = status.lower_bound(point(-1e20, right->second - sqrtOpt));
-			auto upper = status.upper_bound(point(-1e20, right->second + sqrtOpt));
+			auto lower = status.lower_bound(pt(-1e20, right->snd - sqrtOpt));
+			auto upper = status.upper_bound(pt(-1e20, right->snd + sqrtOpt));
 			while (lower != upper) {
 				double cand = squaredDist(*right, *lower);
 				if (cand < opt) {
@@ -30,7 +30,6 @@ double shortestDist(vector<point> &points) {
 				++lower;
 			}
 			status.insert(*(right++));
-		}
-	}
+	}}
 	return sqrtOpt;
 }
-- 
cgit v1.2.3