diff options
| -rw-r--r-- | content/geometry/polygon.cpp | 7 | ||||
| -rw-r--r-- | content/graph/euler.cpp | 29 | ||||
| -rw-r--r-- | test/graph/euler.cpp | 8 |
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]); } |