From e8356c886f8431adf2ebeede299896947372e4b4 Mon Sep 17 00:00:00 2001 From: Yidi Date: Tue, 28 Jan 2025 15:12:53 +0100 Subject: shorter euler tour --- content/graph/euler.cpp | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) (limited to 'content') diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index a5ea192..fff9371 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -1,23 +1,18 @@ -vector> idx; -vector to, validIdx, cycle; -vector used; +vector>> adj; +vector cycle; void addEdge(int u, int v) { - idx[u].push_back(sz(to)); - to.push_back(v); - used.push_back(false); - idx[v].push_back(sz(to)); // für ungerichtet - to.push_back(u); - used.push_back(false); + adj[u].emplace_back(v, sz(adj[v])); + adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for undirected } -void euler(int v) { // init idx und validIdx - for (;validIdx[v] < sz(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 == -1) continue; + adj[u][rev].first = -1; // remove for undirected + euler(u); + } cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge. } -- cgit v1.2.3 From 0c55282e01f07dd6bad486b591b156f7e9aa8fa7 Mon Sep 17 00:00:00 2001 From: Yidi Date: Tue, 28 Jan 2025 15:16:03 +0100 Subject: fix pdf line break --- content/graph/euler.cpp | 2 +- tcr.pdf | Bin 695526 -> 703218 bytes 2 files changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index fff9371..f375d42 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -3,7 +3,7 @@ vector cycle; void addEdge(int u, int v) { adj[u].emplace_back(v, sz(adj[v])); - adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for undirected + adj[v].emplace_back(u, sz(adj[u])-1); // remove for undirected } void euler(int v) { diff --git a/tcr.pdf b/tcr.pdf index 157dbc4..2aa3284 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 9682f525a3f4c07de062f940233cec734543e8a7 Mon Sep 17 00:00:00 2001 From: Yidi Date: Tue, 28 Jan 2025 15:32:21 +0100 Subject: fix comments --- content/graph/euler.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'content') diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index f375d42..0b39f53 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -3,15 +3,15 @@ vector cycle; void addEdge(int u, int v) { adj[u].emplace_back(v, sz(adj[v])); - adj[v].emplace_back(u, sz(adj[u])-1); // remove for undirected + adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for directed } void euler(int v) { while (!adj[v].empty()) { auto [u, rev] = adj[v].back(); adj[v].pop_back(); - if (u == -1) continue; - adj[u][rev].first = -1; // remove for undirected + if (u == -1) continue; // remove for directed + adj[u][rev].first = -1; // remove for directed euler(u); } cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge. -- cgit v1.2.3 From 939e434ae205af10cccb4ce8e4103e9ec3f1e7a1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Wed, 12 Feb 2025 11:11:10 +0100 Subject: added comment --- content/graph/euler.cpp | 4 ++-- tcr.pdf | Bin 703218 -> 699076 bytes 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'content') diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index 0b39f53..e81cebe 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -1,4 +1,4 @@ -vector>> adj; +vector>> adj; // gets destroyed! vector cycle; void addEdge(int u, int v) { @@ -10,7 +10,7 @@ void euler(int v) { while (!adj[v].empty()) { auto [u, rev] = adj[v].back(); adj[v].pop_back(); - if (u == -1) continue; // remove for directed + if (u < 0) continue; // remove for directed adj[u][rev].first = -1; // remove for directed euler(u); } diff --git a/tcr.pdf b/tcr.pdf index 2aa3284..34cf09c 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From d91ac762cdb3e4c30cdeaf7a078ae5a8d32ed489 Mon Sep 17 00:00:00 2001 From: Yidi Date: Wed, 12 Feb 2025 17:12:09 +0100 Subject: fix comment --- content/geometry/polygon.cpp | 7 +++---- tcr.pdf | Bin 699076 -> 703380 bytes 2 files changed, 3 insertions(+), 4 deletions(-) (limited to 'content') diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 064d81f..1332a4a 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -23,14 +23,13 @@ ll windingNumber(pt p, const vector& 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& poly) { bool in = false; for (int i = 0; i + 1 < sz(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/tcr.pdf b/tcr.pdf index 34cf09c..76c898a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3