diff options
| -rw-r--r-- | datastructures/datastructures.tex | 4 | ||||
| -rw-r--r-- | datastructures/treap2.cpp | 78 | ||||
| -rw-r--r-- | geometry/formulars.cpp | 6 | ||||
| -rw-r--r-- | geometry/linesAndSegments.cpp | 4 | ||||
| -rw-r--r-- | geometry/polygon.cpp | 16 | ||||
| -rw-r--r-- | tcr.pdf | bin | 645307 -> 662433 bytes |
6 files changed, 94 insertions, 14 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 8d1cb02..c39a2c6 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -58,8 +58,8 @@ \sourcecode{datastructures/firstUnused.cpp} \end{algorithm} -\begin{algorithm}{Treap (Cartesian Tree)} - \sourcecode{datastructures/treap.cpp} +\begin{algorithm}{(Implicit) Treap (Cartesian Tree)} + \sourcecode{datastructures/treap2.cpp} \end{algorithm} \begin{algorithm}[optional]{Range Minimum Query} diff --git a/datastructures/treap2.cpp b/datastructures/treap2.cpp new file mode 100644 index 0000000..5d0aefa --- /dev/null +++ b/datastructures/treap2.cpp @@ -0,0 +1,78 @@ +mt19937 rng(0xc4bd5dad); +struct Treap { + struct Node { + ll val; + int prio, size = 1, l = -1, r = -1; + Node (ll x) : val(x), prio(rng()) {} + }; + + vector<Node> treap; + int root = -1; + + int getSize(int v) { + return v < 0 ? 0 : treap[v].size; + } + + void upd(int v) { + if (v < 0) return; + auto *V = &treap[v]; + V->size = 1 + getSize(V->l) + getSize(V->r); + // Update Node Code + } + + void push(int v) { + if (v < 0) return; + //auto *V = &treap[v]; + //if (V->lazy) { + // Lazy Propagation Code + // if (V->l >= 0) treap[V->l].lazy = true; + // if (V->r >= 0) treap[V->r].lazy = true; + // V->lazy = false; + //} + } + + pair<int, int> split(int v, int k) { + if (v < 0) return {-1, -1}; + auto *V = &treap[v]; + push(v); + if (getSize(V->l) >= k) { // "V->val >= k" for lower_bound(k) + auto [left, right] = split(V->l, k); + V->l = right; + upd(v); + return {left, v}; + } else { + auto [left, right] = split(V->r, k - getSize(V->l) - 1); // and only "k" + V->r = left; + upd(v); + return {v, right}; + }} + + int merge(int left, int right) { + if (left < 0) return right; + if (right < 0) return left; + if (treap[left].prio < treap[right].prio) { + push(left); + treap[left].r = merge(treap[left].r, right); + upd(left); + return left; + } else { + push(right); + treap[right].l = merge(left, treap[right].l); + upd(right); + return right; + }} + + void insert(int i, ll val) { // and i = val + auto [left, right] = split(root, i); + treap.emplace_back(val); + left = merge(left, sz(treap) - 1); + root = merge(left, right); + } + + void remove(int i, int count = 1) { + auto [left, t_right] = split(root, i); + auto [middle, right] = split(t_right, count); + root = merge(left, right); + } + // for query use remove and read middle BEFORE remerging +}; diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp index 855ef1e..37cc4f4 100644 --- a/geometry/formulars.cpp +++ b/geometry/formulars.cpp @@ -21,9 +21,9 @@ double norm(pt a) {return dot(a, a);} double cross(pt a, pt b) {return imag(conj(a) * b);} double cross(pt p, pt a, pt b) {return cross(a - p, b - p);} -// -1 => gegen den Uhrzeigersinn -// 0 => kolliniear -// 1 => im Uhrzeigersinn. +// 1 => c links von a->b +// 0 => a, b und c kolliniear +// -1 => c rechts von a->b int orientation(pt a, pt b, pt c) { double orien = cross(b - a, c - a); return (orien > EPS) - (orien < -EPS); diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp index 3a8ac02..4da35b1 100644 --- a/geometry/linesAndSegments.cpp +++ b/geometry/linesAndSegments.cpp @@ -39,7 +39,7 @@ double distToLine(pt a, pt b, pt p) { // Liegt p auf der Geraden a-b? 2d und 3d bool pointOnLine(pt a, pt b, pt p) { - return orientation(a, b, p) == 0; + return cross(a, b, p) == 0; } // Test auf Linienschnitt zwischen a-b und c-d. @@ -57,7 +57,7 @@ pt lineIntersection(pt p0, pt p1, pt p2, pt p3) { // Liegt p auf der Strecke a-b? bool pointOnLineSegment(pt a, pt b, pt p) { - if (orientation(a, b, p) != 0) return false; + if (cross(a, b, p) != 0) return false; ld dist = norm(a - b); return norm(a - p) <= dist && norm(b - p) <= dist; } diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp index 3a633af..1620d7c 100644 --- a/geometry/polygon.cpp +++ b/geometry/polygon.cpp @@ -2,13 +2,15 @@ // Punkte gegen den Uhrzeigersinn: positiv, sonst negativ. double area(const vector<pt>& poly) { //poly[0] == poly.back() double res = 0; - for (int i = 0; i + 1 < n; i++) + for (int i = 0; i + 1 < sz(poly); i++) res += cross(poly[i], poly[i + 1]); return 0.5 * res; } // Anzahl drehungen einer Polyline um einen Punkt // p nicht auf rand und poly[0] == poly.back() +// res != 0 or (res & 1) != 0 um inside zu prüfen bei +// selbstschneidenden polygonen (definitions sache) ll windingNumber(pt p, const vector<pt>& poly) { ll res = 0; for (int i = 0; i + 1 < sz(poly); i++) { @@ -22,12 +24,12 @@ ll windingNumber(pt p, const vector<pt>& poly) { } // Testet, ob ein Punkt im Polygon liegt (beliebige Polygone). -// Ändere Zeile 31 falls rand zählt, poly[0] == poly.back() +// Ändere Zeile 32 falls rand zählt, poly[0] == poly.back() 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, b)) return false; + if (pointOnLineSegment(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) { @@ -37,16 +39,16 @@ bool inside(pt p, const vector<pt>& poly) { } // convex hull without duplicates, h[0] == h.back() -// Change line 43 and 49 >= if border counts as inside +// Change line 45 and 51 >= if border counts as inside bool inside(pt p, const vector<pt>& hull) { int l = 0, r = sz(hull) - 1; - if (orientation(hull[0], hull[r], p) > 0) return false; + if (cross(hull[0], hull[r], p) > 0) return false; while (l + 1 < r) { int m = (l + r) / 2; - if (orientation(hull[0], hull[m], p) >= 0) l = m; + if (cross(hull[0], hull[m], p) >= 0) l = m; else r = m; } - return orientation(hull[l], hull[r], p) > 0; + return cross(hull[l], hull[r], p) > 0; } void rotateMin(vector<pt>& hull) { Binary files differ |