adding closest pair algorithm

1 files changed, 37 insertions, 0 deletions

diff --git a/geometry/closestPair.cpp b/geometry/closestPair.cpp
new file mode 100644
index 0000000..10c9291
--- /dev/null
+++ b/geometry/closestPair.cpp
@@ -0,0 +1,37 @@
+double squaredDist(point a, point b) {
+	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
+}
+
+bool compY(point a, point b) {
+	if (a.second == b.second) {
+		return a.first < b.first;
+	}
+	return a.second < b.second;
+}
+
+void shortestDist(vector<point> &points) {
+	//check that points.size() > 1 and that ALL POINTS ARE DIFFERENT
+	set<point, bool(*)(point, point)> 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) {
+			status.erase(*(left++));
+		} else {
+			auto lower = status.lower_bound(point(-1e20, right->second - sqrtOpt));
+			auto upper = status.upper_bound(point(-1e20, right->second + sqrtOpt));
+			while (lower != upper) {
+				double cand = squaredDist(*right, *lower);
+				if (cand < opt) {
+					opt = cand;
+					sqrtOpt = sqrt(opt);
+				}
+				++lower;
+			}
+			status.insert(*(right++));
+		}
+	} // closest distance in sqrtOpt
+}