merge mzuenni changes

2 files changed, 15 insertions, 21 deletions

diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp
index 9c90534..474ce88 100644
--- a/content/geometry/polygon.cpp
+++ b/content/geometry/polygon.cpp
@@ -23,14 +23,13 @@ ll windingNumber(pt p, const vector<pt>& poly) {
 	return res;
 }
 
-// Testet, ob ein Punkt im Polygon liegt (beliebige Polygone).
-// Ändere Zeile 32 falls rand zählt, poly[0] == poly.back()
+// check if point is inside polygon (any polygon)
 bool inside(pt p, const vector<pt>& poly) {
 	bool in = false;
 	for (int i = 0; i + 1 < ssize(poly); i++) {
 		pt a = poly[i], b = poly[i + 1];
-		if (pointOnSegment(a, b, p)) return false;
-		if (real(a) > real(b)) swap(a,b);
+		if (pointOnSegment(a, b, p)) return false; // border counts?
+		if (real(a) > real(b)) swap(a, b);
 		if (real(a) <= real(p) && real(p) < real(b) &&
 		    cross(p, a, b) < 0) {
 			in ^= 1;
diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp
index c506d58..d45dac0 100644
--- a/content/graph/euler.cpp
+++ b/content/graph/euler.cpp
@@ -1,23 +1,18 @@
-vector<vector<int>> idx;
-vector<int> to, validIdx, cycle;
-vector<bool> used;
+vector<vector<pair<int, int>>> adj; // gets destroyed!
+vector<int> cycle;
 
 void addEdge(int u, int v) {
-	idx[u].push_back(ssize(to));
-	to.push_back(v);
-	used.push_back(false);
-	idx[v].push_back(ssize(to)); // für ungerichtet
-	to.push_back(u);
-	used.push_back(false);
+	adj[u].emplace_back(v, ssize(adj[v]));
+	adj[v].emplace_back(u, ssize(adj[u]) - 1); // remove for directed
 }
 
-void euler(int v) { // init idx und validIdx
-	for (;validIdx[v] < ssize(idx[v]); validIdx[v]++) {
-		if (!used[idx[v][validIdx[v]]]) {
-			int u = to[idx[v][validIdx[v]]];
-			used[idx[v][validIdx[v]]] = true;
-			used[idx[v][validIdx[v]] ^ 1] = true; // für ungerichtet
-			euler(u);
-	}}
+void euler(int v) {
+	while (!adj[v].empty()) {
+		auto [u, rev] = adj[v].back();
+		adj[v].pop_back();
+		if (u < 0) continue; // remove for directed
+		adj[u][rev].first = -1; // remove for directed
+		euler(u);
+	}
 	cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge.
 }