From 04703be68216170849bfe5151319ec962d3d072b Mon Sep 17 00:00:00 2001
From: pjungeblut <paul.jungeblut@gmail.com>
Date: Sat, 25 Oct 2014 17:43:08 +0200
Subject: adding closest pair algorithm

---
 geometry/closestPair.cpp |  37 +++++++++++++++++++++++++++++++++++++
 geometry/geometry.tex    |   4 ++++
 maxFlow/edmondsKarp.cpp  |   9 ++++-----
 tcr.pdf                  | Bin 0 -> 45262 bytes
 tcr.tex                  |   1 +
 5 files changed, 46 insertions(+), 5 deletions(-)
 create mode 100644 geometry/closestPair.cpp
 create mode 100644 geometry/geometry.tex
 create mode 100644 tcr.pdf

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
+}
diff --git a/geometry/geometry.tex b/geometry/geometry.tex
new file mode 100644
index 0000000..7a72526
--- /dev/null
+++ b/geometry/geometry.tex
@@ -0,0 +1,4 @@
+\section{Geometry}
+
+\subsection{Closest Pair}
+\lstinputlisting{geometry/closestPair.cpp}
\ No newline at end of file
diff --git a/maxFlow/edmondsKarp.cpp b/maxFlow/edmondsKarp.cpp
index c82b141..a2be9a6 100644
--- a/maxFlow/edmondsKarp.cpp
+++ b/maxFlow/edmondsKarp.cpp
@@ -1,7 +1,7 @@
 int s, t, f; //source, target, single flow
-int res[100][100]; //adj-matrix
+int res[MAX_V][MAX_V]; //adj-matrix
 vector< vector<int> > adjList;
-int p[100]; //bfs spanning tree
+int p[MAX_V]; //bfs spanning tree
 
 void augment(int v, int minEdge) {
 	if (v == s) { f = minEdge; return; }
@@ -10,12 +10,11 @@ void augment(int v, int minEdge) {
 		res[p[v]][v] -= f; res[v][p[v]] += f;
 }}
 
-int main() {
-	//inititalize res, adjList, s, t
+int main() { //first inititalize res, adjList, s and t
 	int mf = 0;
 	while (true) {
 		f = 0;
-		bitset<100> vis; vis[s] = true;
+		bitset<MAX_V> vis; vis[s] = true;
 		queue<int> q; q.push(s);
 		memset(p, -1, sizeof(p));
 		while (!q.empty()) { //BFS
diff --git a/tcr.pdf b/tcr.pdf
new file mode 100644
index 0000000..9f6d1b1
Binary files /dev/null and b/tcr.pdf differ
diff --git a/tcr.tex b/tcr.tex
index 2ac5f75..254a422 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -41,5 +41,6 @@
 \begin{document}
 
 \input{maxFlow/maxFlow}
+\input{geometry/geometry}
 
 \end{document}
\ No newline at end of file
-- 
cgit v1.2.3