Merge branch 'new-master' of github.com:mzuenni/ContestReference into new-master

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) {
diff --git a/tcr.pdf b/tcr.pdf
index f25ba66..496b1da 100644
--- a/tcr.pdf
+++ b/tcr.pdf