Closest Pair done in C++!

Finally Divide and Conquer section is finished. A lot of work but so
much fun!

A few take aways:
1. Be careful when copying code over from Java to C++. Java does
parameter passing through reference as default, but I forgot to add "&"
in C++ code, which caused my code not passing earlier;
2. Avoid unnecessary calculation. For example, the sqrt calculation is
not necessary, until the last step. Avoiding that in my Python code
saved a lot of time.
3. It seems that preallocate vector size, if you know beforehand, is a
good idea.

Woohoo, onto the next section!

2 files changed, 148 insertions, 74 deletions

diff --git a/PlaygroundCpp/.settings/language.settings.xml b/PlaygroundCpp/.settings/language.settings.xml
index aa6e0c9..1410d72 100644
--- a/PlaygroundCpp/.settings/language.settings.xml
+++ b/PlaygroundCpp/.settings/language.settings.xml
@@ -5,7 +5,7 @@
 			<provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/>
 			<provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/>
 			<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
-			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939321890483387581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
 				<language-scope id="org.eclipse.cdt.core.gcc"/>
 				<language-scope id="org.eclipse.cdt.core.g++"/>
 			</provider>
@@ -16,7 +16,7 @@
 			<provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/>
 			<provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/>
 			<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
-			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939321890483387581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
 				<language-scope id="org.eclipse.cdt.core.gcc"/>
 				<language-scope id="org.eclipse.cdt.core.g++"/>
 			</provider>
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index dbb916c..d3330a1 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,97 +1,171 @@
-#include <algorithm>
 #include <iostream>
-#include <climits>
 #include <vector>
+#include <cmath>
+#include <iomanip>
+#include <algorithm>
+#include <cfloat>
 //#include <gtest/gtest.h>
 
 using std::vector;
+using std::min;
 
-struct Segment {
-	int start, end;
-	bool operator==(const Segment &s1) {
-		return (start == s1.start && end == s1.end);
+struct Point {
+	int x, y;
+	bool operator==(const Point &p1) {
+		return (x == p1.x && y == p1.y);
 	}
 };
 
-bool sortSeg(Segment i, Segment j) {
-	if (i.start == j.start) {
-		return i.end < j.end;
+bool sortPointXDimension(Point i, Point j) {
+	if (i.x == j.x) {
+		return i.y < j.y;
 	}
-	return i.start < j.start;
+	return i.x < j.x;
 }
-vector<int> fast_count_segments(vector<int> starts, vector<int> ends,
-		vector<int> points) {
-	// Implement algo described here, really clever:
-	// https://www.coursera.org/learn/algorithmic-toolbox/discussions/all/threads/QJ1jK9wNEeWdPBL2iFTrAw/replies/Ihiw4txhEeWK5g7mfcS2Xw/comments/oyAMaeIiEeWyqwpvChh66Q
-	// l->1, p->2, r->3 for Segment.end property
-	vector<Segment> s(starts.size() + ends.size() + points.size());
-	vector<Segment> p(points.size());
-	Segment tempSeg;
-	for (int i = 0; i < p.size(); i++) {
-		tempSeg = {points[i], i};
-		p[i] = tempSeg;
-		tempSeg = {points[i], 2};
-		s[2 * starts.size() + i] = tempSeg;
+
+bool sortPointYDimension(Point i, Point j) {
+	if (i.y == j.y) {
+		return i.x < j.x;
 	}
-	for (int i = 0; i < starts.size(); i++) {
-		tempSeg = {starts[i], 1};
-		s[i] = tempSeg;
-		tempSeg = {ends[i], 3};
-		s[i + starts.size()] = tempSeg;
+	return i.y < j.y;
+}
+
+float distance(Point p1, Point p2) {
+	return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2);
+}
+
+float baseCaseMinDistance(vector<Point> &ptsVector, int low, int high) {
+	if (high - low == 1)
+		return distance(ptsVector[low], ptsVector[high]);
+	if (high - low == 2) {
+		float f1 = distance(ptsVector[low], ptsVector[low + 1]);
+		float f2 = distance(ptsVector[low], ptsVector[high]);
+		float f3 = distance(ptsVector[high], ptsVector[low + 1]);
+		return min(f1, min(f2, f3));
 	}
-	std::sort(s.begin(), s.end(), sortSeg);
-	std::sort(p.begin(), p.end(), sortSeg);
-	vector<int> results(points.size());
-	int count = 0;
-	int j = 0;
-	for (int i = 0; i < s.size(); i++) {
-		if (s[i].end == 1) {
-			count = count + 1;
-		}
-		if (s[i].end == 2) {
-			results[j] = count;
-			j = j + 1;
-		}
-		if (s[i].end == 3) {
-			count = count - 1;
+	float f1 = distance(ptsVector[low], ptsVector[low + 1]);
+	float f2 = distance(ptsVector[low], ptsVector[low + 2]);
+	float f3 = distance(ptsVector[low], ptsVector[high]);
+	float f4 = distance(ptsVector[low + 1], ptsVector[low + 2]);
+	float f5 = distance(ptsVector[low + 1], ptsVector[high]);
+	float f6 = distance(ptsVector[low + 2], ptsVector[high]);
+	return min(f1, min(f2, min(f3, min(f4, min(f5, f6)))));
+}
+
+float dPrimeDistance(vector<Point> &shadedPoints) {
+	float minDistance = FLT_MAX;
+	float tempDistance;
+	for (int i = 0; i < shadedPoints.size(); i++) {
+		for (int j = 1; j <= 5; j++) {
+			if (i + j < shadedPoints.size()) {
+				tempDistance = distance(shadedPoints[i], shadedPoints[i + j]);
+				minDistance = min(tempDistance, minDistance);
+			}
 		}
 	}
-	vector<int> finalResults(points.size());
-	for (int i = 0; i < finalResults.size(); i++) {
-		finalResults[p[i].end] = results[i];
+	return minDistance;
+}
+
+float minimalDistance(vector<Point> &ptsVector, int low, int high) {
+	if (high - low <= 3) {
+		return baseCaseMinDistance(ptsVector, low, high);
+	}
+	int mid = low + (high - low) / 2;
+	long midX = ptsVector[mid].x;
+	float f1 = minimalDistance(ptsVector, low, mid - 1);
+	float f2 = minimalDistance(ptsVector, mid, high);
+	float f = min(f1, f2);
+	vector<Point> shadedPoints;
+	for (int i = low; i <= high; i++) {
+		if (abs(ptsVector[i].x - midX) <= f)
+			shadedPoints.push_back(ptsVector[i]);
 	}
-	return finalResults;
+
+	std::sort(shadedPoints.begin(), shadedPoints.end(), sortPointYDimension);
+
+	float fPrime = dPrimeDistance(shadedPoints);
+
+	return min(f, fPrime);
 }
+float minimalDistance(vector<int> &x, vector<int> &y) {
+	vector<Point> ptsVector(x.size());
+	Point tempP;
+
+	for (int i = 0; i < x.size(); i++) {
+		tempP = {x[i],y[i]};
+		ptsVector[i] = tempP;
+	}
 
-//TEST(SortSegment, Sort1) {
-//	vector<int> starts = { 0, 7 };
-//	vector<int> ends = { 5, 10 };
-//	vector<int> points = { 1, 6, 11 };
-//	vector<int> results = { 1, 0, 0 };
+	std::sort(ptsVector.begin(), ptsVector.end(), sortPointXDimension);
+	return sqrt(minimalDistance(ptsVector, 0, ptsVector.size() - 1));
+}
+//TEST(SortPoint, Sort1) {
+//	vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 };
+//	vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 };
+//	vector<Point> p;
+//	Point tempP;
+//
+//	for (int i = 0; i < x.size(); ++i) {
+//		tempP = {x[i],y[i]};
+//		p.push_back(tempP);
+//	};
+//
+//	std::sort(p.begin(), p.end(), sortPointXDimension);
+//
+//	ASSERT_EQ(p[0].x, -4);
+//	ASSERT_EQ(p[0].y, 0);
+//
+//	std::sort(p.begin(), p.end(), sortPointYDimension);
+//	ASSERT_EQ(p[0].y, -4);
+//	ASSERT_EQ(p[0].x, -3);
+//	ASSERT_EQ(p[10].y, 4);
+//	ASSERT_EQ(p[10].x, 4);
+//}
+//
+//TEST(PointDistance, Test1) {
+//	vector<int> x = { 0, 0 };
+//	vector<int> y = { 3, 4 };
+//
+//	float f = minimalDistance(x, y);
+//	ASSERT_FLOAT_EQ(f, 5);
+//}
 //
-//	vector<int> cnt = fast_count_segments(starts, ends, points);
+//TEST(ClosestDistance, Test1) {
+//	vector<int> x = { 0, 3 };
+//	vector<int> y = { 0, 4 };
+//	float result = 5.0;
+//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
+//}
 //
-//	ASSERT_EQ(cnt[0], 1);
-//	ASSERT_EQ(cnt[1], 0);
-//	ASSERT_EQ(cnt[2], 0);
-//	ASSERT_EQ(cnt.size(), 3);
+//TEST(ClosestDistance, Test2) {
+//	vector<int> x = { 0, 3, 5 };
+//	vector<int> y = { 0, 4, 6 };
+//	float result = 2.828427;
+//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
+//}
+//
+//TEST(ClosestDistance, Test3) {
+//	vector<int> x = { 7, 1, 4, 7 };
+//	vector<int> y = { 7, 100, 8, 7 };
+//	float result = 0.0;
+//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
+//}
+//
+//TEST(ClosestDistance, Test4) {
+//	vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 };
+//	vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 };
+//	float result = 1.4142135;
+//	ASSERT_FLOAT_EQ(result, minimalDistance(x, y));
 //}
 
 int main() {
-  int n, m;
-  std::cin >> n >> m;
-  vector<int> starts(n), ends(n);
-  for (size_t i = 0; i < starts.size(); i++) {
-    std::cin >> starts[i] >> ends[i];
-  }
-  vector<int> points(m);
-  for (size_t i = 0; i < points.size(); i++) {
-    std::cin >> points[i];
-  }
-  //use fast_count_segments
-  vector<int> cnt = fast_count_segments(starts, ends, points);
-  for (size_t i = 0; i < cnt.size(); i++) {
-    std::cout << cnt[i] << ' ';
+  size_t n;
+  std::cin >> n;
+  vector<int> x(n);
+  vector<int> y(n);
+  for (size_t i = 0; i < n; i++) {
+    std::cin >> x[i] >> y[i];
   }
+  std::cout << std::fixed;
+  std::cout << std::setprecision(9) << minimalDistance(x, y) << "\n";
 }
-