merge mzuenni changes

3 files changed, 19 insertions, 25 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.
 }
diff --git a/test/graph/euler.cpp b/test/graph/euler.cpp
index e468e05..353cff2 100644
--- a/test/graph/euler.cpp
+++ b/test/graph/euler.cpp
@@ -1,6 +1,6 @@
 #include "../util.h"
 struct Euler {
-	Euler(int n) : idx(n), validIdx(n) {}
+	Euler(int n) : adj(n) {}
 #include <graph/euler.cpp>
 };
 
@@ -20,7 +20,7 @@ Euler eulerGraph(int n, int m) {
 	}
 	int last = -1;
 	for (int i = 0; i < n; i++) {
-		if (ssize(res.idx[i]) % 2 != 0) {
+		if (ssize(res.adj[i]) % 2 != 0) {
 			if (last >= 0) {
 				res.addEdge(last, i);
 				last = -1;
@@ -44,8 +44,8 @@ void stress_test() {
 
 		vector<vector<int>> expected(n);
 		for (int i = 0; i < n; i++) {
-			for (int j : g.idx[i]) {
-				expected[i].push_back(g.to[j]);
+			for (auto [j, rev] : g.adj[i]) {
+				expected[i].push_back(j);
 			}
 			ranges::sort(expected[i]);
 		}