diff options
| -rw-r--r-- | geometry/closestPair.cpp | 25 | ||||
| -rw-r--r-- | tcr.pdf | bin | 257382 -> 257221 bytes |
2 files changed, 12 insertions, 13 deletions
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; } Binary files differ |