Typesetting for convex hull code.

1 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];
   }