added new code

5 files changed, 73 insertions, 5 deletions

diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp
index ef70fb5..2607aae 100644
--- a/geometry/polygon.cpp
+++ b/geometry/polygon.cpp
@@ -71,3 +71,65 @@ double dist(const vector<pt>& ps, const vector<pt>& qs) {
 	}
 	return res;
 }
+
+bool left(pt of, pt p) {return cross(p, of) < 0 || 
+                       (cross(p, of) == 0 && dot(p, of) > 0);}
+
+// convex hulls without duplicates, poly[0] == poly.back() and
+// poly[0] must be a convex point (with angle < pi)
+// returns index of corner where dot(dir, corner) is maximized
+int extremal(const vector<pt>& poly, pt dir) {
+	dir *= pt(0, 1);
+	int l = 0;
+	int r = sz(poly) - 1;
+	while (l + 1 < r) {
+		int m = (l + r) / 2;
+		pt dm = poly[m+1]-poly[m];
+		pt dl = poly[l+1]-poly[l];
+		if (left(dl, dir) != left(dl, dm)) {
+			if (left(dl, dm)) l = m;
+			else r = m;
+		} else {
+			if (cross(dir, dm) < 0) l = m;
+			else r = m;
+	}}
+	return r;
+}
+
+// convex hulls without duplicates, poly[0] == poly.back() and
+// poly[0] must be a convex point (with angle < pi)
+// {} if no intersection
+// {x} if corner is only intersection
+// {a, b} segments (a,a+1) and (b,b+1) intersected (if only the
+// border is intersected corners a and b are the start and end)
+vector<int> intersect(const vector<pt>& poly, pt a, pt b) {
+	int endA = extremal(poly, (a-b) * pt(0, 1));
+	int endB = extremal(poly, (b-a) * pt(0, 1));
+
+	// cross == 0 => line only intersects border
+	if (cross(poly[endA], a, b) > 0 ||
+	    cross(poly[endB], a, b) < 0) return {};
+
+	int n = sz(poly) - 1;
+	vector<int> res;
+	for (auto _ : {0, 1}) {
+		int l = endA;
+		int r = endB;
+		if (r < l) r += n;
+		while (l+1 < r) {
+			int m = (l + r) / 2;
+			if (cross(poly[m % n], a, b) <= 0 &&
+			    cross(poly[m % n], a, b) != cross(poly[endB], a, b)) {
+				l = m;
+			} else {
+				r = m;
+		}}
+		if (cross(poly[r % n], a, b) == 0) l++;
+		res.push_back(l % n);
+		swap(endA, endB);
+		swap(a, b);
+	}
+	if (res[0] == res[1]) res.pop_back();
+	return res;
+}
+
diff --git a/math/math.tex b/math/math.tex
index d637e0c..27b3c8a 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -141,16 +141,13 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \end{algorithm}
 
 \begin{algorithm}{Primzahltest \& Faktorisierung}
-	\begin{itemize}
-		\item für $n > 10^9$ \texttt{BigInteger} benutzten order \texttt{modMul}! 
-	\end{itemize}
 	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
 	\sourcecode{math/millerRabin.cpp}
 	\columnbreak
 	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
 	\sourcecode{math/rho.cpp}
-	\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
-	\sourcecode{math/squfof.cpp}
+	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
+	%\sourcecode{math/squfof.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
diff --git a/other/other.tex b/other/other.tex
index 1a56919..a5a05b0 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -78,6 +78,9 @@
 	
 	\paragraph{Quadrangle inequality} Die Bedingung  $\forall a\leq b\leq c\leq d:
 	C[a][d] + C[b][c] \geq C[a][c] + C[b][d]$ ist hinreichend für beide Optimierungen.
+	
+	\paragraph{Sum over Subsets DP} $\text{res}[\text{mask}]=\sum_{i\subseteq\text{mask}}\text{in}[i]$
+		\sourcecode{other/sos.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Parallel Binary Search}
diff --git a/other/sos.cpp b/other/sos.cpp
new file mode 100644
index 0000000..0fe5dc0
--- /dev/null
+++ b/other/sos.cpp
@@ -0,0 +1,6 @@
+vector<ll> res(in);
+for (int i = 1; i < sz(res); i *= 2) {
+	for (int mask = 0; mask < sz(res); mask++){
+		if (mask & i) {
+			F[mask] += F[mask ^ i];
+}}}
diff --git a/tcr.pdf b/tcr.pdf
index 83429b2..5de8426 100644
--- a/tcr.pdf
+++ b/tcr.pdf