merge mzuenni changes

8 files changed, 48 insertions, 48 deletions

diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp
index 6d89e05..1173924 100644
--- a/content/geometry/convexHull.cpp
+++ b/content/geometry/convexHull.cpp
@@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){
 			while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--;
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/content/geometry/formulas3d.cpp b/content/geometry/formulas3d.cpp
index dee3ce8..63de2ce 100644
--- a/content/geometry/formulas3d.cpp
+++ b/content/geometry/formulas3d.cpp
@@ -26,23 +26,23 @@ int ccw(pt3 a, pt3 b, pt3 c, pt3 p) {
 	return (orien > EPS) - (orien < -EPS);
 }
 
-// Entfernung von Punkt p zur Ebene a,b,c.
+// Entfernung von Punkt p zur Ebene a, b, c.
 double distToPlane(pt3 a, pt3 b, pt3 c, pt3 p) {
-	pt3 n = cross(b-a, c-a);
-	return (abs(dot(n, p)) - dot(n, a)) / abs(n);
+	pt3 n = cross(b - a, c - a);
+	return abs(dot(n, a - p)) / abs(n);
 }
 
-// Liegt p in der Ebene a,b,c?
+// Liegt p in der Ebene a, b, c?
 bool pointOnPlane(pt3 a, pt3 b, pt3 c, pt3 p) {
 	return ccw(a, b, c, p) == 0;
 }
 
-// Schnittpunkt von der Grade a-b und der Ebene c,d,e
+// Schnittpunkt von der Grade a-b und der Ebene c, d, e
 // die Grade darf nicht parallel zu der Ebene sein!
 pt3 linePlaneIntersection(pt3 a, pt3 b, pt3 c, pt3 d, pt3 e) {
-	pt3 n = cross(d-c, e-c);
-	pt3 d = b - a;
-	return a - d * (dot(n, a) - dot(n, c)) / dot(n, d);
+	pt3 n = cross(d - c, e - c);
+	pt3 dir = b - a;
+	return a + dir * dot(n, c - a) / dot(n, dir);
 }
 
 // Abstand zwischen der Grade a-b und c-d
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index 3509e0e..02c71e3 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
@@ -27,22 +27,22 @@ struct hp {
 			if (ort == 0) return cross(from, to, a.from) < 0;
 			return cross(b.dir(), a.dir()) * ort > 0;
 		}
-		ll y = cross(a.dir(), b.dir());
-		ll z = cross(b.from - a.from, b.dir());
-		ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
-		// check if i is outside/right of x
-		return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
+		ll x = cross(a.dir(), b.dir());
+		ll y = cross(b.from - a.from, b.dir());
+		ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b
+		// check if i is outside/right of this
+		return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0;
 	}
 };
 
 constexpr ll lim = 2e9+7;
 
 deque<hp> intersect(vector<hp> hps) {
-	hps.push_back(hp(pt{lim+1,-1}));
-	hps.push_back(hp(pt{lim+1,1}));
+	hps.push_back(hp(pt{lim + 1, -1}));
+	hps.push_back(hp(pt{lim + 1, 1}));
 	sort(all(hps));
 
-	deque<hp> dq = {hp(pt{-lim, 1})};
+	deque<hp> dq = {hp(pt{-lim - 1, 1})};
 	for (auto x : hps) {
 		while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
 			dq.pop_back();
@@ -60,7 +60,7 @@ deque<hp> intersect(vector<hp> hps) {
 
 	while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2]))
 		dq.pop_back();
-	while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1]))
+	while (sz(dq) > 2 && dq.back().check(dq[0], dq[1]))
 		dq.pop_front();
 
 	if (sz(dq) < 3) return {};
diff --git a/content/geometry/lines.cpp b/content/geometry/lines.cpp
index 95536a4..36de1db 100644
--- a/content/geometry/lines.cpp
+++ b/content/geometry/lines.cpp
@@ -1,10 +1,10 @@
 struct line {
-	double a, b, c; // ax + by + c = 0; vertikale Line: b = 0, sonst: b = 1
-	line(pt p, pt q) : a(-imag(q-p)), b(real(q-p)), c(cross({b, -a},p)) {}
+	double a, b, c; // ax + by + c = 0; vertikale Gerade: b = 0
+	line(pt p, pt q) : a(imag(p-q)), b(real(q-p)), c(cross({-b, a}, p)) {}
 };
 
-line pointsToLine(pt p1, pt p2) {
-	line l;
+line pointsToLine(pt p1, pt p2) { // vertikale Gerade: b = 1 oder b = 0
+	line l(0, 0);
 	if (abs(real(p1 - p2)) < EPS) {
 		l.a = 1; l.b = 0.0; l.c = -real(p1);
 	} else {
@@ -15,19 +15,19 @@ line pointsToLine(pt p1, pt p2) {
 	return l;
 }
 
-bool parallel(line l1, line l2) {
+bool parallel(line l1, line l2) { // braucht b in {0, 1}
 	return (abs(l1.a - l2.a) < EPS) && (abs(l1.b - l2.b) < EPS);
 }
 
-bool same(line l1, line l2) {
+bool same(line l1, line l2) { // braucht b in {0, 1}
 	return parallel(l1, l2) && (abs(l1.c - l2.c) < EPS);
 }
 
-bool intersect(line l1, line l2, pt& p) {
+bool intersect(line l1, line l2, pt& res) { // braucht b in {0, 1}
 	if (parallel(l1, l2)) return false;
 	double y, x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
 	if (abs(l1.b) > EPS) y = -(l1.a * x + l1.c);
 	else y = -(l2.a * x + l2.c);
-	p = {x, y};
+	res = {x, y};
 	return true;
 }
diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp
index 1e21cba..ddab554 100644
--- a/content/geometry/linesAndSegments.cpp
+++ b/content/geometry/linesAndSegments.cpp
@@ -5,7 +5,7 @@ bool pointOnLine(pt a, pt b, pt p) {
 
 // Test auf Linienschnitt zwischen a-b und c-d. (nicht identisch)
 bool lineIntersection(pt a, pt b, pt c, pt d) {
-	return abs(cross(a - b, c - d)) < EPS;
+	return abs(cross(a - b, c - d)) > EPS;
 }
 
 // Berechnet den Schnittpunkt der Graden a-b und c-d.
diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp
index 3178290..064d81f 100644
--- a/content/geometry/polygon.cpp
+++ b/content/geometry/polygon.cpp
@@ -29,7 +29,7 @@ bool inside(pt p, const vector<pt>& poly) {
 	bool in = false;
 	for (int i = 0; i + 1 < sz(poly); i++) {
 		pt a = poly[i], b = poly[i + 1];
-		if (pointOnLineSegment(a, b, p)) return false;
+		if (pointOnSegment(a, b, p)) return false;
 		if (real(a) > real(b)) swap(a,b);
 		if (real(a) <= real(p) && real(p) < real(b) &&
 		    cross(p, a, b) < 0) {
diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp
index 4262ddc..afc01b2 100644
--- a/content/geometry/segmentIntersection.cpp
+++ b/content/geometry/segmentIntersection.cpp
@@ -18,8 +18,8 @@ struct event {
 	int id, type;
 	bool operator<(const event& o) const {
 		if (real(p) != real(o.p)) return real(p) < real(o.p);
-		if (type != o.type) return type > o.type;
-		return imag(p) < imag(o.p);
+		if (imag(p) != imag(o.p)) return imag(p) < imag(o.p);
+		return type > o.type;
 	}
 };
 
@@ -29,7 +29,7 @@ bool lessPT(const pt& a, const pt& b) {
 }
 
 bool intersect(const seg& a, const seg& b) {
-	return lineSegmentIntersection(a.a, a.b, b.a, b.b);
+	return segmentIntersection(a.a, a.b, b.a, b.b); //@\sourceref{geometry/linesAndSegments.cpp}@
 }
 
 pair<int, int> intersect(vector<seg>& segs) {
diff --git a/content/geometry/spheres.cpp b/content/geometry/spheres.cpp
index ec22262..d34bca9 100644
--- a/content/geometry/spheres.cpp
+++ b/content/geometry/spheres.cpp
@@ -1,3 +1,16 @@
+// 3D Punkt in kartesischen Koordinaten.
+struct point{
+	double x, y, z;
+	point() {}
+	point(double x, double y, double z) : x(x), y(y), z(z) {}
+	point(double lat, double lon) {
+		lat *= PI / 180.0; lon *= PI / 180.0;
+		x = cos(lat) * sin(lon);
+		y = cos(lat) * cos(lon);
+		z = sin(lat);
+	}
+};
+
 // Great Circle Distance mit Längen- und Breitengrad.
 double gcDist(double pLat, double pLon,
 	          double qLat, double qLon, double radius) {
@@ -11,19 +24,6 @@ double gcDist(double pLat, double pLon,
 }
 
 // Great Circle Distance mit kartesischen Koordinaten.
-double gcDist(point p, point q) {
+double gcDist(point p, point q) { // radius = 1
 	return acos(p.x * q.x + p.y * q.y + p.z * q.z);
-}
-
-// 3D Punkt in kartesischen Koordinaten.
-struct point{
-	double x, y, z;
-	point() {}
-	point(double x, double y, double z) : x(x), y(y), z(z) {}
-	point(double lat, double lon) {
-		lat *= PI / 180.0; lon *= PI / 180.0;
-		x = cos(lat) * sin(lon);
-		y = cos(lat) * cos(lon);
-		z = sin(lat);
-	}
-};
+}
\ No newline at end of file