diff options
| -rw-r--r-- | geometry/convexHull.cpp | 15 | ||||
| -rw-r--r-- | tcr.pdf | bin | 257067 -> 256865 bytes |
2 files changed, 4 insertions, 11 deletions
diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp index 7ff270b..69bbfdf 100644 --- a/geometry/convexHull.cpp +++ b/geometry/convexHull.cpp @@ -1,29 +1,22 @@ // Laufzeit: O(n*log(n)) -typedef pair<ll, ll> pt; -// >0 => PAB dreht gegen den Uhrzeigersinn. -// <0 => PAB dreht im Uhrzeigersinn. -// =0 => PAB sind kollinear. ll cross(const pt p, const pt a, const pt b) { - return (a.first - p.first) * (b.second - p.second) - - (a.second - p.second) * (b.first - p.first); + return (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x); } // Punkte auf der konvexen Hülle, gegen den Uhrzeigersinn sortiert. -// Kollineare Punkte sind nicht enthalten. Entferne "=" im CCW-Test um sie aufzunehmen. +// Kollineare Punkte nicht enthalten, entferne dafür "=" im CCW-Test. // Achtung: Der erste und letzte Punkt im Ergebnis sind gleich. // Achtung: Alle Punkte müssen verschieden sein. vector<pt> convexHull(vector<pt> p){ int n = p.size(), k = 0; vector<pt> h(2 * n); sort(p.begin(), p.end()); - // Untere Hülle. - for (int i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { // Untere Hülle. while (k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0.0) k--; h[k++] = p[i]; } - // Obere Hülle. - for (int i = n - 2, t = k + 1; i >= 0; i--) { + for (int i = n - 2, t = k + 1; i >= 0; i--) { // Obere Hülle. while (k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0.0) k--; h[k++] = p[i]; } Binary files differ |