diff options
| -rw-r--r-- | geometry/closestPair.cpp | 37 | ||||
| -rw-r--r-- | geometry/geometry.tex | 4 | ||||
| -rw-r--r-- | maxFlow/edmondsKarp.cpp | 9 | ||||
| -rw-r--r-- | tcr.pdf | bin | 0 -> 45262 bytes | |||
| -rw-r--r-- | tcr.tex | 1 |
5 files changed, 46 insertions, 5 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 +} 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 Binary files differ@@ -41,5 +41,6 @@ \begin{document} \input{maxFlow/maxFlow} +\input{geometry/geometry} \end{document}
\ No newline at end of file |