merged

30 files changed, 496 insertions, 316 deletions

diff --git a/datastructures/LCT.cpp b/datastructures/LCT.cpp
index 9adae89..c1dd278 100644
--- a/datastructures/LCT.cpp
+++ b/datastructures/LCT.cpp
@@ -42,7 +42,7 @@ struct LCT {
 
 		bool isRoot() {
 			return !parent || (parent->left != this &&
-			       parent->right != this);
+			                   parent->right != this);
 		}
 
 		void push() {
diff --git a/datastructures/bitset.cpp b/datastructures/bitset.cpp
index 9f33a5b..242d821 100644
--- a/datastructures/bitset.cpp
+++ b/datastructures/bitset.cpp
@@ -1,7 +1,6 @@
 bitset<10> bits(0b000010100);
-cout << bits._Find_first() << endl; //2
-cout << bits._Find_next(2) << endl; //4
-cout << bits._Find_next(4) << endl; //10 bzw. N
-bits[x] = 1;    //not bits.set(x)!
-bits[x] = 0;    //not bits.reset(x)!
-bits[x].flip(); //not bits.flip(x)!
+bits._Find_first(); //2
+bits._Find_next(2); //4
+bits._Find_next(4); //10 bzw. N
+bits[x] = 1;        //not bits.set(x) or bits.reset(x)!
+bits[x].flip();     //not bits.flip(x)!
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 200144c..8f9698c 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -1,15 +1,5 @@
 \section{Datenstrukturen}
 
-\begin{algorithm}{Union-Find}
-	\begin{methods}
-		\method{init}{legt $n$ einzelne Unions an}{n}
-		\method{findSet}{findet den Repräsentanten}{\log(n)}
-		\method{unionSets}{vereint 2 Mengen}{\log(n)}
-		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
-	\end{methods}
-	\sourcecode{datastructures/unionFind.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Segmentbaum}
 	\begin{methods}
 		\method{init}{baut den Baum auf}{n}
@@ -20,15 +10,10 @@
 	
 	\subsubsection{Lazy Propagation}
 	Assignment modifications, sum queries \\
-		\method{lower\_bound}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)}
+	\method{lower\_bound}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)}
 	\sourcecode{datastructures/lazyPropagation.cpp}
 \end{algorithm}
 
-\begin{algorithm}{STL-Bitset}
-	\sourcecode{datastructures/bitset.cpp}
-\end{algorithm}
-\clearpage
-
 \begin{algorithm}{Fenwick Tree}
 	\begin{methods}
 		\method{init}{baut den Baum auf}{n\*\log(n)}
@@ -44,21 +29,10 @@
 	\end{methods}
 	\sourcecode{datastructures/fenwickTree2.cpp}
 \end{algorithm}
+\clearpage
 
-\begin{algorithm}{Wavelet Tree}
-	\begin{methods}
-		\method{Constructor}{baut den Baum auf}{n\*\log(n)}
-		\method{kth}{sort $[l, r)[k]$}{\log(n)}
-		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/waveletTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl}
-	\begin{methods}
-		\method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/firstUnused.cpp}
+\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
+	\sourcecode{datastructures/stlRope.cpp}
 \end{algorithm}
 
 \begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
@@ -69,15 +43,6 @@
 	\sourcecode{datastructures/treap2.cpp}
 \end{algorithm}
 
-\begin{algorithm}[optional]{Range Minimum Query}
-	\begin{methods}
-		\method{init}{baut Struktur auf}{n\*\log(n)}
-		\method{query}{Index des Minimums in [l, r)}{1}
-	\end{methods}
-	\sourcecode{datastructures/RMQ.cpp}
-\end{algorithm}
-
-\needspace{5\baselineskip}%
 \begin{algorithm}{Range Minimum Query}
 	\begin{methods}
 		\method{init}{baut Struktur auf}{n\*\log(n)}
@@ -89,32 +54,19 @@
 	\sourcecode{datastructures/sparseTable.cpp}
 \end{algorithm}
 
-\begin{algorithm}{STL-Tree}
-	\sourcecode{datastructures/stlTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
-	\sourcecode{datastructures/stlRope.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL HashMap}
-	3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
-	\sourcecode{datastructures/stlHashMap.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL Priority Queue}
-	Nicht notwendig, wenn Smaller-Larger-Optimization greift.
-	\sourcecode{datastructures/stlPQ.cpp}
+\begin{algorithm}{Wavelet Tree}
+	\begin{methods}
+		\method{Constructor}{baut den Baum auf}{n\*\log(n)}
+		\method{kth}{sort $[l, r)[k]$}{\log(n)}
+		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/waveletTree.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)}
-	Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
-	\sourcecode{datastructures/monotonicConvexHull.cpp}
-	\sourcecode{datastructures/dynamicConvexHull.cpp}
+\begin{algorithm}{STL-Bitset}
+	\sourcecode{datastructures/bitset.cpp}
 \end{algorithm}
 
-\clearpage
-
 \begin{algorithm}{Link-Cut-Tree}
 	\begin{methods}
 		\method{Constructor}{baut Wald auf}{n}
@@ -127,8 +79,25 @@
 	\end{methods}
 	\sourcecode{datastructures/LCT.cpp}
 \end{algorithm}
-
 \clearpage
+
+\begin{algorithm}{Union-Find}
+	\begin{methods}
+		\method{init}{legt $n$ einzelne Unions an}{n}
+		\method{findSet}{findet den Repräsentanten}{\log(n)}
+		\method{unionSets}{vereint 2 Mengen}{\log(n)}
+		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
+	\end{methods}
+	\sourcecode{datastructures/unionFind.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)}
+	Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
+	\sourcecode{datastructures/monotonicConvexHull.cpp}
+	\columnbreak
+	\sourcecode{datastructures/dynamicConvexHull.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Persistent}
 	\begin{methods}
 		\method{get}{berechnet Wert zu Zeitpunkt $t$}{\log(t)}
@@ -138,3 +107,35 @@
 	\sourcecode{datastructures/persistent.cpp}
 	\sourcecode{datastructures/persistentArray.cpp}
 \end{algorithm}
+
+\begin{algorithm}{STL-Tree}
+	\sourcecode{datastructures/stlTree.cpp}
+\end{algorithm}
+
+\begin{algorithm}{STL Priority Queue}
+	Nicht notwendig, wenn Smaller-Larger-Optimization greift.
+	\sourcecode{datastructures/stlPQ.cpp}
+\end{algorithm}
+
+\begin{algorithm}{STL HashMap}
+	3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
+	\sourcecode{datastructures/stlHashMap.cpp}
+\end{algorithm}
+
+
+
+\begin{algorithm}[optional]{Range Minimum Query}
+	\begin{methods}
+		\method{init}{baut Struktur auf}{n\*\log(n)}
+		\method{query}{Index des Minimums in [l, r)}{1}
+	\end{methods}
+	\sourcecode{datastructures/RMQ.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl}
+	\begin{methods}
+		\method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/firstUnused.cpp}
+\end{algorithm}
+
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
index 4b3dbff..0049b3d 100644
--- a/datastructures/monotonicConvexHull.cpp
+++ b/datastructures/monotonicConvexHull.cpp
@@ -1,6 +1,7 @@
 // Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
 // Gerade hat kleinere Steigung als alle vorherigen.
-vector<ll> ms, bs; int ptr = 0;
+vector<ll> ms, bs;
+int ptr = 0;
 
 bool bad(int l1, int l2, int l3) {
 	return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) <
diff --git a/datastructures/persistent.cpp b/datastructures/persistent.cpp
index 1704ff2..0a65a79 100644
--- a/datastructures/persistent.cpp
+++ b/datastructures/persistent.cpp
@@ -7,12 +7,11 @@ struct persistent {
 		: time(time), data(1, {time, value}) {}

 	

 	T get(int t) {

-		return prev(upper_bound(all(data), 

-		                        pair<int, T>(t+1, {})))->second;

+		return prev(upper_bound(all(data), {t+1, {}}))->second;

 	}

 	

 	int set(T value) {

-		time+=2;

+		time += 2;

 		data.push_back({time, value});

 		return time;

 	}

diff --git a/datastructures/persistentArray.cpp b/datastructures/persistentArray.cpp
index 2db0e73..60d8b17 100644
--- a/datastructures/persistentArray.cpp
+++ b/datastructures/persistentArray.cpp
@@ -1,15 +1,13 @@
 template<typename T>

-struct persistentArray{

-	int time = 0;

+struct persistentArray {

+	int time;

 	vector<persistent<T>> data;

 	vector<pair<int, int>> mods;

 

 	persistentArray(int n, T value = {}) 

 		: time(0), data(n, {time, value}) {}

 

-	T get(int p, int t) {

-		return data[p].get(t);

-	}

+	T get(int p, int t) {return data[p].get(t);}

 

 	int set(int p, T value) {

 		mods.push_back({p, time});

diff --git a/datastructures/stlPQ.cpp b/datastructures/stlPQ.cpp
index b48223b..4e439f8 100644
--- a/datastructures/stlPQ.cpp
+++ b/datastructures/stlPQ.cpp
@@ -5,11 +5,11 @@ using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>;
 
 int main() {
 	priorityQueue<int> pq;
-	auto it = pq.push(5); // O(1)
+	auto it = pq.push(5);   // O(1)
 	pq.push(7);
-	pq.pop(); // O(log n) amortisiert
-	pq.modify(it, 6); // O(log n) amortisiert
-	pq.erase(it); // O(log n) amortisiert
+	pq.pop();               // O(log n) amortisiert
+	pq.modify(it, 6);       // O(log n) amortisiert
+	pq.erase(it);           // O(log n) amortisiert
 	priorityQueue<int> pq2;
-	pq.join(pq2); // O(1)
+	pq.join(pq2);           // O(1)
 }
diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp
index 0fdc480..fbb68b9 100644
--- a/datastructures/stlTree.cpp
+++ b/datastructures/stlTree.cpp
@@ -7,10 +7,7 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
 
 int main() {
 	Tree<int> X;
-	// insert {1, 2, 4, 8, 16}
-	for (int i = 1; i <= 16; i *= 2) X.insert(i);
-	cout << *X.find_by_order(3) << endl; // => 8
-	cout << X.order_of_key(10) << endl;
-	// => 4 = min i, mit X[i] >= 10
-	return 0;
+	for (int i : {1, 2, 4, 8, 16}) X.insert(i);
+	*X.find_by_order(3); // => 8
+	X.order_of_key(10);  // => 4 = min i, mit X[i] >= 10
 }
diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
index 03ff63e..35843cd 100644
--- a/datastructures/unionFind.cpp
+++ b/datastructures/unionFind.cpp
@@ -12,12 +12,10 @@ int findSet(int n) { // Pfadkompression
 }
 
 void linkSets(int a, int b) { // Union by rank.
-	if (unions[a] > unions[b]) unions[a] = b;
-	else if (unions[b] > unions[a]) unions[b] = a;
-	else {
-		unions[a] = b;
-		unions[b]--;
-}}
+	if (unions[b] > unions[a]) swap(a, b);
+	if (unions[b] == unions[a]) unions[b]--;
+	unions[a] = b;
+}
 
 void unionSets(int a, int b) { // Diese Funktion aufrufen.
 	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp
index 8a0e10f..36c1b56 100644
--- a/datastructures/waveletTree.cpp
+++ b/datastructures/waveletTree.cpp
@@ -3,7 +3,6 @@ struct WaveletTree {
 	WaveletTree *ln, *rn;

 	ll lo, hi;

 	vector<int> b;

-

 private:

 	WaveletTree(it from, it to, ll x, ll y)

 	: ln(nullptr), rn(nullptr), lo(x), hi(y), b(1) {

@@ -17,7 +16,6 @@ private:
 		ln = new WaveletTree(from, pivot, lo, mid);

 		rn = new WaveletTree(pivot, to, mid, hi);

 	}

-

 public:

 	WaveletTree(vector<ll> in) : WaveletTree(all(in), 

 		*min_element(all(in)), *max_element(all(in)) + 1){}

diff --git a/geometry/delaunay.cpp b/geometry/delaunay.cpp
new file mode 100644
index 0000000..1008b39
--- /dev/null
+++ b/geometry/delaunay.cpp
@@ -0,0 +1,124 @@
+using lll = __int128;
+using pt = complex<ll>;
+
+constexpr pt INF_PT = pt(1e18, 1e18);
+
+bool circ(pt p, pt a, pt b, pt c) {// p in circle(A,B,C)
+	return imag((c-b)*conj(p-c)*(a-p)*conj(b-a)) < 0;
+}
+
+struct QuadEdge {
+	QuadEdge* rot = nullptr;
+	QuadEdge* onext = nullptr;
+	pt orig = INF_PT;
+	bool used = false;
+	QuadEdge* rev() const {return rot->rot;}
+	QuadEdge* lnext() const {return rot->rev()->onext->rot;}
+	QuadEdge* oprev() const {return rot->onext->rot;}
+	pt dest() const {return rev()->orig;}
+};
+
+deque<QuadEdge> edgeData;
+
+QuadEdge* makeEdge(pt from, pt to) {
+	for (int j : {0,1,2,3}) edgeData.push_back({});
+	auto e = edgeData.end() - 4;
+	for (int j : {0,1,2,3}) e[j].onext = e[j^3].rot = &e[j^(j>>1)];
+	e[0].orig = from;
+	e[1].orig = to;
+	return &e[0];
+}
+
+void splice(QuadEdge* a, QuadEdge* b) {
+	swap(a->onext->rot->onext, b->onext->rot->onext);
+	swap(a->onext, b->onext);
+}
+
+QuadEdge* connect(QuadEdge* a, QuadEdge* b) {
+	QuadEdge* e = makeEdge(a->dest(), b->orig);
+	splice(e, a->lnext());
+	splice(e->rev(), b);
+	return e;
+}
+
+bool valid(QuadEdge* e, QuadEdge* base) {
+	return cross(e->dest(), base->orig, base->dest()) < 0;
+}
+
+template<bool ccw>
+QuadEdge* deleteAll(QuadEdge* e, QuadEdge* base) {
+	if (valid(e, base)) {
+		while (circ(base->dest(), base->orig, e->dest(), (ccw ? e->onext : e->oprev())->dest())) {
+			QuadEdge* t = ccw ? e->onext : e->oprev();
+			splice(e, e->oprev());
+			splice(e->rev(), e->rev()->oprev());
+			e = t;
+	}}
+	return e;
+}
+
+template<typename IT>
+pair<QuadEdge*, QuadEdge*> rec(IT l, IT r) {
+	int n = distance(l, r);
+	if (n <= 3) {
+		QuadEdge* a = makeEdge(l[0], l[1]);
+		if (n == 2) return {a, a->rev()};
+		QuadEdge* b = makeEdge(l[1], l[2]);
+		splice(a->rev(), b);
+		int side = cross(l[0], l[1], l[2]);
+		QuadEdge* c = nullptr;
+		if (side != 0) c = connect(b, a);
+		if (side >= 0) return {a, b->rev()};
+		else return {c->rev(), c};
+	}
+	auto m = l + (n / 2);
+	auto [ldo, ldi] = rec(l, m);
+	auto [rdi, rdo] = rec(m, r);
+	while (true) {
+		if (cross(rdi->orig, ldi->orig, ldi->dest()) > 0) {
+			ldi = ldi->lnext();
+		} else if (cross(ldi->orig, rdi->orig, rdi->dest()) < 0) {
+			rdi = rdi->rev()->onext;
+		} else break;
+	}
+	QuadEdge* base = connect(rdi->rev(), ldi);
+	if (ldi->orig == ldo->orig)	ldo = base->rev();
+	if (rdi->orig == rdo->orig)	rdo = base;
+	while (true) {
+		QuadEdge* lcand = deleteAll<true>(base->rev()->onext, base);
+		QuadEdge* rcand = deleteAll<false>(base->oprev(), base);
+		if (!valid(lcand, base) && !valid(rcand, base))	break;
+		if (!valid(lcand, base) || (valid(rcand, base) &&
+		    circ(lcand->dest(), lcand->orig, rcand->orig, rcand->dest()))) {
+			base = connect(rcand, base->rev());
+		} else {
+			base = connect(base->rev(), lcand->rev());
+	}}
+	return {ldo, rdo};
+}
+
+vector<pt> delaunay(vector<pt> pts) {
+	if (sz(pts) <= 2) return {};
+	sort(all(pts), [](const pt& a, const pt& b) {
+		if (real(a) != real(b)) return real(a) < real(b);
+		return imag(a) < imag(b);
+	});
+	QuadEdge* r = rec(all(pts)).first;
+	vector<QuadEdge*> edges = {r};
+	while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext;
+	auto add = [&](QuadEdge* e){
+		QuadEdge* cur = e;
+		do {
+			cur->used = true;
+			pts.push_back(cur->orig);
+			edges.push_back(cur->rev());
+			cur = cur->lnext();
+		} while (cur != e);
+	};
+	add(r);
+	pts.clear();
+	for (int i = 0; i < sz(edges); i++) {
+		if (!edges[i]->used) add(edges[i]);
+	}
+	return pts;
+}
diff --git a/geometry/geometry.tex b/geometry/geometry.tex
index a027de4..d92bad1 100644
--- a/geometry/geometry.tex
+++ b/geometry/geometry.tex
@@ -7,14 +7,6 @@
 	\sourcecode{geometry/closestPair.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Rotating calipers}
-	\begin{methods}
-		\method{antipodalPoints}{berechnet antipodale Punkte}{n}
-	\end{methods}
-	\textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn Sortiert sein und konvexes Polygon bilden!
-	\sourcecode{geometry/antipodalPoints.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Konvexe Hülle}
 	\begin{methods}
 		\method{convexHull}{berechnet Konvexehülle}{n\*\log(n)}
@@ -27,23 +19,43 @@
 	\sourcecode{geometry/convexHull.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Rotating calipers}
+	\begin{methods}
+		\method{antipodalPoints}{berechnet antipodale Punkte}{n}
+	\end{methods}
+	\textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn Sortiert sein und konvexes Polygon bilden!
+	\sourcecode{geometry/antipodalPoints.cpp}
+\end{algorithm}
+
 \subsection{Formeln~~--~\texttt{std::complex}}
 \sourcecode{geometry/formulars.cpp}
 \sourcecode{geometry/linesAndSegments.cpp}
+\sourcecode{geometry/sortAround.cpp}
 \input{geometry/triangle}
 \sourcecode{geometry/triangle.cpp}
 \sourcecode{geometry/polygon.cpp}
-\sourcecode{geometry/sortAround.cpp}
 \sourcecode{geometry/circle.cpp}
 
 \subsection{Formeln - 3D}
 \sourcecode{geometry/formulars3d.cpp}
 
 \optional{
-\subsection{3D-Kugeln}
-\sourcecode{geometry/spheres.cpp}
+	\subsection{3D-Kugeln}
+	\sourcecode{geometry/spheres.cpp}
 }
 
+\begin{algorithm}{Half-plane intersection}
+	\sourcecode{geometry/hpi.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Delaunay Triangulierung}
+	\begin{methods}
+		\method{delaunay}{berechnet Triangulierung}{n\*\log(n)}
+	\end{methods}
+	\textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Traingulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig.
+	\sourcecode{geometry/delaunay.cpp}
+\end{algorithm}
+
 \optional{
 \subsection{Geraden}
 \sourcecode{geometry/lines.cpp}
diff --git a/geometry/hpi.cpp b/geometry/hpi.cpp
new file mode 100644
index 0000000..3509e0e
--- /dev/null
+++ b/geometry/hpi.cpp
@@ -0,0 +1,68 @@
+constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+
+bool left(pt p) {return real(p) < 0 || 
+					   (real(p) == 0 && imag(p) < 0);}
+struct hp {
+	pt from, to;
+
+	hp(pt a, pt b) : from(a), to(b) {}
+	hp(pt dummy) : hp(dummy, dummy) {}
+
+	bool dummy() const {return from == to;}
+	pt dir() const {return dummy() ? to : to - from;}
+	bool operator<(const hp& o) const {
+		if (left(dir()) != left(o.dir())) 
+			return left(dir()) > left(o.dir());
+		return cross(dir(), o.dir()) > 0;
+	}
+
+	using lll = __int128;
+	using ptl = complex<lll>;
+	ptl mul(lll m, ptl p) const {return m*p;}//ensure 128bit
+
+	bool check(const hp& a, const hp& b) const {
+		if (dummy() || b.dummy()) return false;
+		if (a.dummy()) {
+			ll ort = sgn(cross(b.dir(), dir()));
+			if (ort == 0) return cross(from, to, a.from) < 0;
+			return cross(b.dir(), a.dir()) * ort > 0;
+		}
+		ll y = cross(a.dir(), b.dir());
+		ll z = cross(b.from - a.from, b.dir());
+		ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
+		// check if i is outside/right of x
+		return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
+	}
+};
+
+constexpr ll lim = 2e9+7;
+
+deque<hp> intersect(vector<hp> hps) {
+	hps.push_back(hp(pt{lim+1,-1}));
+	hps.push_back(hp(pt{lim+1,1}));
+	sort(all(hps));
+
+	deque<hp> dq = {hp(pt{-lim, 1})};
+	for (auto x : hps) {
+		while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
+			dq.pop_back();
+		while (sz(dq) > 1 && x.check(dq[0], dq[1]))
+			dq.pop_front();
+
+		if (cross(x.dir(), dq.back().dir()) == 0) {
+			if (dot(x.dir(), dq.back().dir()) < 0) return {};
+			if (cross(x.from, x.to, dq.back().from) < 0)
+				dq.pop_back();
+			else continue;
+		}
+		dq.push_back(x);
+	}
+
+	while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2]))
+		dq.pop_back();
+	while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1]))
+		dq.pop_front();
+
+	if (sz(dq) < 3) return {};
+	return dq;
+}
diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp
index ba6c468..c86b331 100644
--- a/geometry/linesAndSegments.cpp
+++ b/geometry/linesAndSegments.cpp
@@ -17,8 +17,7 @@ vector<pt> lineSegmentIntersection(pt p0, pt p1, pt p2, pt p3) {
 	double b = cross(p2 - p0, p3 - p2);
 	double c = cross(p1 - p0, p0 - p2);
 	if (a < 0) {a = -a; b = -b; c = -c;}
-	if (b < -EPS || a-b < -EPS ||
-	    c < -EPS || a-c < -EPS) return {};
+	if (b < -EPS || b-a > EPS || c < -EPS || c-a > EPS) return {};
 	if (a > EPS) return {p0 + b/a*(p1 - p0)};
 	vector<pt> result;
 	auto insertUnique = [&](pt p) {
diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp
index f562b7a..409f765 100644
--- a/geometry/polygon.cpp
+++ b/geometry/polygon.cpp
@@ -10,13 +10,13 @@ double area(const vector<pt>& poly) { //poly[0] == poly.back()
 // 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)
+// selbstschneidenden Polygonen (definitions Sache)
 ll windingNumber(pt p, const vector<pt>& poly) {
 	ll res = 0;
 	for (int i = 0; i + 1 < sz(poly); i++) {
 		pt a = poly[i], b = poly[i + 1];
-		if (real(a) > real(b)) swap(a,b);
-		if (real(a) <= real(p) &&real(p) < real(b) &&
+		if (real(a) > real(b)) swap(a, b);
+		if (real(a) <= real(p) && real(p) < real(b) &&
 		    cross(p, a, b) < 0) {
 			res += orientation(p, poly[i], poly[i + 1]);
 	}}
diff --git a/geometry/triangle.cpp b/geometry/triangle.cpp
index a00eb56..ebbbc88 100644
--- a/geometry/triangle.cpp
+++ b/geometry/triangle.cpp
@@ -28,12 +28,17 @@ pt outCenter(pt a, pt b, pt c) {
 	        c*conj(c)*conj(a-b)) / d;
 }
 
+//  1 => p außerhalb Kreis durch a,b,c
+//  0 => p auf Kreis durch a,b,c
+// -1 => p im Kreis durch a,b,c
+int insideOutCenter(pt a, pt b, pt c, pt p) {// braucht lll
+	return sgn(imag((c-b)*conj(p-c)*(a-p)*conj(b-a)));
+}
+
 // Sind die Dreiecke a1, b1, c1, and a2, b2, c2 ähnlich?
 // Erste Zeile testet Ähnlichkeit mit gleicher Orientierung,
 // zweite Zeile testet Ähnlichkeit mit verschiedener Orientierung
-bool similar (pt a1, pt b1, pt c1, pt a2, pt b2, pt c2) {
-	return ((b2-a2) * (c1-a1) == (b1-a1) * (c2-a2) ||
-	        (b2-a2) * (conj(c1)-conj(a1)) == (conj(b1)-conj(a1))
-			* (c2-a2)
-	);
+bool similar(pt a1, pt b1, pt c1, pt a2, pt b2, pt c2) {
+	return (b2-a2) * (c1-a1) == (b1-a1) * (c2-a2) ||
+	       (b2-a2) * conj(c1-a1) == conj(b1-a1) * (c2-a2);
 }
diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp
index 7ba51c0..4324886 100644
--- a/graph/bellmannFord.cpp
+++ b/graph/bellmannFord.cpp
@@ -14,6 +14,4 @@ void bellmannFord(int n, vector<edge> edges, int start) {
 		if (dist[e.from] != INF &&
 		    dist[e.from] + e.cost < dist[e.to]) {
 			// Negativer Kreis gefunden.
-	}}
-	//return dist, parent;
-}
+}}} //return dist, parent?;
diff --git a/graph/bronKerbosch.cpp b/graph/bronKerbosch.cpp
index caf2421..ceeb668 100644
--- a/graph/bronKerbosch.cpp
+++ b/graph/bronKerbosch.cpp
@@ -9,7 +9,7 @@ void bronKerboschRec(bits R, bits P, bits X) {
 	if (!P.any() && !X.any()) {
 		cliques.push_back(R);
 	} else {
-		int q = (P | X)._Find_first();
+		int q = min(P._Find_first(), X._Find_first());
 		bits cands = P & ~adj[q];
 		for (int i = 0; i < sz(adj); i++) if (cands[i]){
 			R[i] = 1;
diff --git a/graph/graph.tex b/graph/graph.tex
index f2ad3e7..e299dd7 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,33 +1,27 @@
 \section{Graphen}
 
-\begin{algorithm}{DFS}
-	\input{graph/dfs}
-\end{algorithm}
-
-\begin{algorithm}{Minimale Spannbäume}
-	\paragraph{Schnitteigenschaft}
-	Für jeden Schnitt $C$ im Graphen gilt:
-	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
-	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
-	
-	\paragraph{Kreiseigenschaft}
-	Für jeden Kreis $K$ im Graphen gilt:
-	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
-\end{algorithm}
-
-\begin{algorithm}{Kruskal}
-	\begin{methods}[ll]
-		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+\begin{algorithm}{Eulertouren}
+	\begin{methods}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
 	\end{methods}
-	\sourcecode{graph/kruskal.cpp}
+	\sourcecode{graph/euler.cpp}
+	\begin{itemize}
+		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
+		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
 \end{algorithm}
 
-\begin{algorithm}{Erd\H{o}s-Gallai}
-	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
+\begin{algorithm}{Lowest Common Ancestor}
 	\begin{methods}
-		\method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})}
+		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
+		\method{getLCA}{findet LCA}{1}
+		\method{getDepth}{berechnet Distanz zur Wurzel im DFS-Baum}{1}
 	\end{methods}
-	\sourcecode{graph/havelHakimi.cpp}
+	\sourcecode{graph/LCA_sparse.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Centroids}
@@ -37,24 +31,52 @@
 	\sourcecode{graph/centroid.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Heavy-Light Decomposition}
+	\begin{methods}
+		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+	\end{methods}
+	\textbf{Wichtig:} Intervalle sind halboffen
+	
+	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
+	\sourcecode{graph/hld.cpp}
+\end{algorithm}
+\clearpage
+
 \begin{algorithm}{Baum-Isomorphie}
 	\begin{methods}
 		\method{treeLabel}{berechnet kanonischen Namen für einen Baum}{\abs{V}\*\log(\abs{V})}
 	\end{methods}
 	\sourcecode{graph/treeIsomorphism.cpp}
 \end{algorithm}
-\clearpage
 
-\subsection{Kürzeste Wege}
+\begin{algorithm}{Minimale Spannbäume}
+	\paragraph{Schnitteigenschaft}
+	Für jeden Schnitt $C$ im Graphen gilt:
+	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
+	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
+	
+	\paragraph{Kreiseigenschaft}
+	Für jeden Kreis $K$ im Graphen gilt:
+	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
+\end{algorithm}
 
-\subsubsection{Algorithmus von \textsc{Dijkstra}}
-\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})}
-\sourcecode{graph/dijkstra.cpp}
+\begin{algorithm}{Kruskal}
+	\begin{methods}[ll]
+		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+	\end{methods}
+	\sourcecode{graph/kruskal.cpp}
+\end{algorithm}
+
+\subsection{Kürzeste Wege}
 
 \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
 \method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}}
 \sourcecode{graph/bellmannFord.cpp}
 
+\subsubsection{Algorithmus von \textsc{Dijkstra}}
+\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})}
+\sourcecode{graph/dijkstra.cpp}
+
 \subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
 \method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3}
 \begin{itemize}
@@ -64,37 +86,31 @@
 \sourcecode{graph/floydWarshall.cpp}
 
 \subsubsection{Matrix-Algorithmus}
-Sei $d_{ij}$ die Distanzmatrix von $G$, dann gibt $d_{ij}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{ij} = a_{ij} * b_{ij} = \min\{a_{ik} + b_{kj}\}$
+Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \min\{a_{ik} + b_{k\smash{j}}\}$
 
 
-Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{ij}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{ij} = a_{ij} \* b_{ij} = \sum a_{ik} + b_{kj}$
+Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$
 
-\begin{algorithm}{Lowest Common Ancestor}
+
+\begin{algorithm}{Erd\H{o}s-Gallai}
+	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
 	\begin{methods}
-		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
-		\method{getLCA}{findet LCA}{1}
-		\method{getDepth}{berechnet Distanz zur Wurzel im DFS-Baum}{1}
+		\method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})}
 	\end{methods}
-	\sourcecode{graph/LCA_sparse.cpp}
+	\sourcecode{graph/havelHakimi.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Heavy-Light Decomposition}
+\begin{algorithm}{Dynamic Connectivity}
 	\begin{methods}
-		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
 	\end{methods}
-	\textbf{Wichtig:} Intervalle sind halboffen
-	
-	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
-	\sourcecode{graph/hld.cpp}
+	\sourcecode{graph/connect.cpp}
 \end{algorithm}
-\clearpage
 
-\begin{algorithm}{Maximal Cliques}
-	\begin{methods}
-		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
-		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
-	\end{methods}
-	\sourcecode{graph/bronKerbosch.cpp}
+\begin{algorithm}{DFS}
+	\input{graph/dfs}
 \end{algorithm}
 
 \begin{algorithm}{Artikulationspunkte, Brücken und BCC}
@@ -116,6 +132,60 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/2sat.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Maximal Cliques}
+	\begin{methods}
+		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
+		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
+	\end{methods}
+	\sourcecode{graph/bronKerbosch.cpp}
+\end{algorithm}
+\clearpage
+
+\begin{algorithm}{Cycle Counting}
+	\begin{methods}
+		\method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
+		\method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
+	\end{methods}
+	\begin{itemize}
+		\item jeder Zyklus ist das xor von einträgen in \code{base}.
+	\end{itemize}
+	\sourcecode{graph/cycleCounting.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Wert des maximalen Matchings}
+	Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$
+	\sourcecode{graph/matching.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Allgemeines maximales Matching}
+	\begin{methods}
+		\method{match}{berechnet algemeines Matching}{\abs{E}\*\abs{V}\*\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/blossom.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
+	\label{kuhn}
+	\begin{methods}
+		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
+	\end{methods}
+	\begin{itemize}
+		\item die ersten [0..n) Knoten in \code{adjlist} sind die linke Seite des Graphen
+	\end{itemize}
+	\sourcecode{graph/maxCarBiMatch.cpp}
+	\begin{methods}
+		\method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}}
+	\end{methods}
+	\sourcecode{graph/hopcroftKarp.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Maximum Weight Bipartite Matching}
+	\begin{methods}
+		\method{match}{berechnet Matching}{\abs{V}^3}
+	\end{methods}
+	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Global Mincut}
 	\begin{methods}
 		\method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}^2\*\log(\abs{E})}
@@ -178,87 +248,16 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
-	\label{kuhn}
-	\begin{methods}
-		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
-	\end{methods}
-	\begin{itemize}
-		\item die ersten [0..n) Knoten in \code{adjlist} sind die linke Seite des Graphen
-	\end{itemize}
-	\sourcecode{graph/maxCarBiMatch.cpp}
-	\begin{methods}
-		\method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}}
-	\end{methods}
-	\sourcecode{graph/hopcroftKarp.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Maximum Weight Bipartite Matching}
-	\begin{methods}
-		\method{match}{berechnet Matching}{\abs{V}^3}
-	\end{methods}
-	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Wert des maximalen Matchings}
-	Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$
-	\sourcecode{graph/matching.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Allgemeines maximales Matching}
-	\begin{methods}
-		\method{match}{berechnet algemeines Matching}{\abs{E}\*\abs{V}\*\log(\abs{V})}
-	\end{methods}
-	\sourcecode{graph/blossom.cpp}
-\end{algorithm}
-
-\optional{
-\begin{algorithm}{TSP}
+\begin{algorithm}[optional]{TSP}
 	\begin{methods}
 		\method{TSP}{berechnet eine Tour}{n^2\*2^n}
 	\end{methods}
 	\sourcecode{graph/TSP.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Bitonic TSP}
+\begin{algorithm}[optional]{Bitonic TSP}
 	\begin{methods}
 		\method{bitonicTSP}{berechnet eine Bitonische Tour}{n^2}
 	\end{methods}
 	\sourcecode{graph/bitonicTSPsimple.cpp}
 \end{algorithm}
-}
-
-\begin{algorithm}{Cycle Counting}
-	\begin{methods}
-		\method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
-		\method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
-	\end{methods}
-	\begin{itemize}
-		\item jeder Zyklus ist das xor von einträgen in \code{base}.
-	\end{itemize}
-	\sourcecode{graph/cycleCounting.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Eulertouren}
-	\begin{methods}
-		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
-	\end{methods}
-	\sourcecode{graph/euler.cpp}
-	\begin{itemize}
-		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
-		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
-		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
-		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
-		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-		Die Existenz muss separat geprüft werden.
-	\end{itemize}
-\end{algorithm}
-
-\begin{algorithm}{Dynamic Connectivity}
-	\begin{methods}
-		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
-		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
-		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
-	\end{methods}
-	\sourcecode{graph/connect.cpp}
-\end{algorithm}
diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp
index 8d5d6ab..6246fe0 100644
--- a/graph/havelHakimi.cpp
+++ b/graph/havelHakimi.cpp
@@ -5,14 +5,12 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) {
 	while (!pq.empty()) {
 		auto [degV, v] = pq.top(); pq.pop();
 		if (sz(pq) < degV) return {}; //impossible
-		vector<pair<int, int>> todo;
-		for (int i = 0; i < degV; i++) {
-			auto [degU, v] = pq.top(); pq.pop();
+		vector<pair<int, int>> todo(degV);
+		for (auto& e : todo) e = pq.top(), pq.pop();
+		for (auto [degU, u] : todo) {
 			adj[v].push_back(u);
 			adj[u].push_back(v);
-			if (degU > 1) todo.push_back({degU - 1, u});
-		}
-		for (auto e : todo) pq.push(e);
-	}
+			if (degU > 1) pq.push({degU - 1, u});
+	}}
 	return adj;
 }
diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp
index 5b0e153..d21da01 100644
--- a/graph/kruskal.cpp
+++ b/graph/kruskal.cpp
@@ -1,6 +1,6 @@
 sort(all(edges));
 vector<edge> mst;
-int cost = 0;
+ll cost = 0;
 for (edge& e : edges) {
 	if (findSet(e.from) != findSet(e.to)) {
 		unionSets(e.from, e.to);
diff --git a/graph/matching.cpp b/graph/matching.cpp
index ddd1c81..2deb672 100644
--- a/graph/matching.cpp
+++ b/graph/matching.cpp
@@ -1,32 +1,9 @@
 constexpr int MOD=1'000'000'007, I=10;
 vector<vector<ll>> adjlist, mat;
 
-int gauss(int n, ll p) {
-	int rank = n;
-	for (int line = 0; line < n; line++) {
-		int swappee = line;
-		while (swappee < n && mat[swappee][line] == 0) swappee++;
-		if (swappee == n) {rank--; continue;}
-		swap(mat[line], mat[swappee]);
-		ll factor = powMod(mat[line][line], p - 2, p);
-		for (int i = 0; i < n; i++) {
-			mat[line][i] *= factor;
-			mat[line][i] %= p;
-		}
-		for (int i = 0; i < n; i++) {
-			if (i == line) continue;
-			ll diff = mat[i][line];
-			for (int j = 0; j < n; j++) {
-				mat[i][j] -= (diff * mat[line][j]) % p;
-				mat[i][j] %= p;
-				if (mat[i][j] < 0) mat[i][j] += p;
-	}}}
-	return rank;
-}
-
 int max_matching() {
 	int ans = 0;
-	mat.assign(sz(adjlist), vector<ll>(sz(adjlist)));
+	mat.assign(sz(adjlist), {});
 	for (int _ = 0; _ < I; _++) {
 		for (int i = 0; i < sz(adjlist); i++) {
 			mat[i].assign(sz(adjlist), 0);
@@ -35,7 +12,12 @@ int max_matching() {
 					mat[i][j] = rand() % (MOD - 1) + 1;
 					mat[j][i] = MOD - mat[i][j];
 		}}}
-		ans = max(ans, gauss(sz(adjlist), MOD)/2);
+		gauss(sz(adjlist), MOD); //LGS unten
+		int rank = 0;
+		for (auto& row : mat) {
+			if (*min_element(all(row)) != 0) rank++;
+		}
+		ans = max(ans, rank / 2);
 	}
 	return ans;
 }
diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp
index 27f6b34..d6d0586 100644
--- a/graph/minCostMaxFlow.cpp
+++ b/graph/minCostMaxFlow.cpp
@@ -23,13 +23,15 @@ struct MinCostFlow {
 	}
 
 	bool SPFA() {
-		pref.assign(sz(adjlist), - 1);
+		pref.assign(sz(adjlist), -1);
 		dist.assign(sz(adjlist), INF);
 		vector<bool> inqueue(sz(adjlist));
 		queue<int> queue;
 
-		dist[s] = 0; queue.push(s);
-		pref[s] = s; inqueue[s] = true;
+		dist[s] = 0;
+		queue.push(s);
+		pref[s] = s;
+		inqueue[s] = true;
 
 		while (!queue.empty()) {
 			int cur = queue.front(); queue.pop();
@@ -39,9 +41,11 @@ struct MinCostFlow {
 				if (edges[id].f > 0 &&
 				    dist[to] > dist[cur] + edges[id].cost) {
 					dist[to] = dist[cur] + edges[id].cost;
-					pref[to] = cur; con[to] = id;
+					pref[to] = cur;
+					con[to] = id;
 					if (!inqueue[to]) {
-						inqueue[to] = true; queue.push(to);
+						inqueue[to] = true;
+						queue.push(to);
 		}}}}
 		return pref[t] != -1;
 	}
diff --git a/latexHeaders/layout.sty b/latexHeaders/layout.sty
index 1c8dc00..096cf23 100644
--- a/latexHeaders/layout.sty
+++ b/latexHeaders/layout.sty
@@ -79,3 +79,4 @@
 }
 
 \usepackage{needspace}
+\usepackage{setspace}
diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp
index 29ec849..7dcd354 100644
--- a/math/lgsFp.cpp
+++ b/math/lgsFp.cpp
@@ -12,7 +12,7 @@ void takeAll(int n, int line, ll p) {
 			mat[i][j] = (mat[i][j] + p) % p;
 }}}
 
-void gauss(int n, ll mod) { // Nx(N+1)-Matrix, Körper F_p.
+void gauss(int n, ll mod) {
 	vector<bool> done(n, false);
 	for (int i = 0; i < n; i++) {
 		int j = 0;
diff --git a/math/permIndex.cpp b/math/permIndex.cpp
index 09ff7f7..4cffc12 100644
--- a/math/permIndex.cpp
+++ b/math/permIndex.cpp
@@ -6,9 +6,8 @@ ll permIndex(vector<ll> v) {
 		x = t.order_of_key(x);
 	}
 	ll res = 0;
-	for (ll i = sz(v); i > 0; i--) {
-		res *= i;
-		res += v[i - 1];
+	for (int i = sz(v); i > 0; i--) {
+		res = res * i + v[i - 1];
 	}
 	return res;
 }
diff --git a/other/bitOps.cpp b/other/bitOps.cpp
index 98fc994..8079305 100644
--- a/other/bitOps.cpp
+++ b/other/bitOps.cpp
@@ -5,9 +5,9 @@ for (int subset = bitmask; subset > 0;
 
 // Zählt Anzahl der gesetzten Bits.
 int numberOfSetBits(int i) {
-	i = i - ((i >> 1) & 0x55555555);
-	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
-	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
+	i = i - ((i >> 1) & 0x5555'5555);
+	i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333);
+	return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 24;
 }
 
 // Nächste Permutation in Bitmaske
diff --git a/other/other.tex b/other/other.tex
index cc89503..58c87a7 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -8,6 +8,11 @@
 	\sourcecode{other/compiletime.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Timed}
+	Kann benutzt werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.
+	\sourcecode{other/timed.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Bit Operations}
 	\begin{expandtable}
 	\begin{tabularx}{\linewidth}{|Ll|}
@@ -39,9 +44,8 @@
 	\end{expandtable}
 \end{algorithm}
 
-\begin{algorithm}{Timed}
-	Kann benutzt werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.
-	\sourcecode{other/timed.cpp}
+\begin{algorithm}{Pragmas}
+	\sourcecode{other/pragmas.cpp}
 \end{algorithm}
 
 \begin{algorithm}{DP Optimizations}
@@ -99,10 +103,6 @@
 	\sourcecode{other/fastIO.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Pragmas}
-	\sourcecode{other/pragmas.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Sonstiges}
 	\sourcecode{other/stuff.cpp}
 \end{algorithm}
diff --git a/string/suffixAutomaton.cpp b/string/suffixAutomaton.cpp
index 8b79822..4cc2a92 100644
--- a/string/suffixAutomaton.cpp
+++ b/string/suffixAutomaton.cpp
@@ -3,57 +3,57 @@ constexpr char OFFSET = 'a';
 struct SuffixAutomaton {
 	struct State {
 		int len, link = -1;
-		int nxt[ALPHABET_SIZE] = {}; // map if large Alphabet
+		array<int, ALPHABET_SIZE> next = {}; // map if large Alphabet
 		State(int l) : len(l) {}
 	};
 
-	vector<State> st{0};
-	int last = 0;
+	vector<State> st = {State(0)};
+	int cur = 0;
 
-	SuffixAutomaton(const string &s) {
+	SuffixAutomaton(const string& s) {
 		st.reserve(2 * sz(s));
 		for (auto c : s) extend(c - OFFSET);
 	}
 
 	void extend(int c) {
-		st.emplace_back(st[last].len + 1);
-		int p = last, cur = last = sz(st) - 1;
-		for (; p != -1 && !st[p].nxt[c]; p = st[p].link) {
-			st[p].nxt[c] = cur;
+		int p = cur;
+		int cur = sz(st);
+		st.emplace_back(st[p].len + 1);
+		for (; p != -1 && !st[p].next[c]; p = st[p].link) {
+			st[p].next[c] = cur;
 		}
 		if (p == -1) st[cur].link = 0;
 		else {
-			int q = st[p].nxt[c];
+			int q = st[p].next[c];
 			if (st[p].len + 1 == st[q].len) {
 				st[cur].link = q;
 			} else {
 				st.emplace_back(st[p].len + 1);
 				st.back().link = st[q].link;
-				copy(all(st[q].nxt), st.back().nxt); // back.nxt=[q].nxt
-				for (; p != -1 && st[p].nxt[c] == q; p = st[p].link) {
-					st[p].nxt[c] = sz(st) - 1;
+				st.back().next = st[q].next;
+				for (; p != -1 && st[p].next[c] == q; p = st[p].link) {
+					st[p].next[c] = sz(st) - 1;
 				}
 				st[q].link = st[cur].link = sz(st) - 1;
-		}}
-	}
+	}}}
 
 	vector<int> calculateTerminals() {
 		vector<int> terminals;
-		for (int p = last; p != -1; p = st[p].link) {
+		for (int p = cur; p != -1; p = st[p].link) {
 			terminals.push_back(p);
 		}
 		return terminals;
 	}
 
 	// Pair with start index (in t) and length of LCS.
-	pair<int, int> longestCommonSubstring(const string &t) {
-		int v = 0, l = 0, best = 0, bestpos = 0;
+	pair<int, int> longestCommonSubstring(const string& t) {
+		int v = 0, l = 0, best = 0, bestp = 0;
 		for (int i = 0; i < sz(t); i++) {
 			int c = t[i] - OFFSET;
-			for (; v && !st[v].nxt[c]; v = st[v].link) l = st[v].len;
-			if (st[v].nxt[c]) v = st[v].nxt[c], l++;
-			if (l > best) best = l, bestpos = i;
+			for (; v && !st[v].next[c]; v = st[v].link) l = st[v].len;
+			if (st[v].next[c]) v = st[v].next[c], l++;
+			if (l > best) best = l, bestp = i;
 		}
-		return {bestpos - best + 1, best};
+		return {bestp - best + 1, best};
 	}
 };
diff --git a/tcr.pdf b/tcr.pdf
index e18fce8..9adbc59 100644
--- a/tcr.pdf
+++ b/tcr.pdf