removed sphere geometry added minkowski

4 files changed, 54 insertions, 14 deletions

diff --git a/geometry/geometry.tex b/geometry/geometry.tex
index 1201917..e52e454 100644
--- a/geometry/geometry.tex
+++ b/geometry/geometry.tex
@@ -38,8 +38,10 @@
 \subsection{Formeln - 3D}
 \sourcecode{geometry/formulars3d.cpp}
 
+\optional{
 \subsection{3D-Kugeln}
 \sourcecode{geometry/spheres.cpp}
+}
 
 \optional{
 \subsection{Geraden}
diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp
index 6a8080d..8acd591 100644
--- a/geometry/polygon.cpp
+++ b/geometry/polygon.cpp
@@ -31,3 +31,43 @@ bool inside(pt p, const vector<pt>& hull) {
 	}
 	return orientation(hull[l], hull[r], p) >= 0;
 }
+
+void rotateMin(vector<pt>& hull) {
+	auto mi = min_element(all(hull), [](const pt& a, const pt& b){
+		return real(a) == real(b) ? imag(a) < imag(b)
+															: real(a) < real(b);
+	});
+	rotate(hull.begin(), mi, hull.end());
+}
+
+//convex hulls without duplicates, h[0] != h.back()
+vector<pt> minkowski(vector<pt> ps, vector<pt> qs) {
+	rotateMin(ps);
+	rotateMin(qs);
+	ps.push_back(ps[0]);
+	qs.push_back(qs[0]);
+	ps.push_back(ps[1]);
+	qs.push_back(qs[1]);
+	vector<pt> res;
+	for (ll i = 0, j = 0; i + 2 < sz(ps) || j + 2 < sz(qs);) {
+		res.push_back(ps[i] + qs[j]);
+		auto c = cross(ps[i + 1] - ps[i], qs[j + 1] - qs[j]);
+		if(c <= 0) i++;
+		if(c >= 0) j++;
+	}
+	return res;
+}
+
+//convex hulls without duplicates, h[0] != h.back()
+double dist(const vector<pt>& ps, const vector<pt>& qs) {
+	for (pt& q : qs) q *= -1;
+	auto p = minkowski(ps, qs);
+	p.push_back(p[0]);
+	double res = 0.0;
+	//bool intersect = true;
+	for (ll i = 0; i + 1 < sz(p); i++) {
+		//intersect &= cross(p[i], p[i+1] - p[i]) <= 0;
+		res = max(res, cross(p[i], p[i+1]-p[i]) / abs(p[i+1]-p[i]));
+	}
+	return res;
+}
diff --git a/math/math.tex b/math/math.tex
index 4545927..6d3d3f2 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -267,21 +267,20 @@ Multipliziert Polynome $A$ und $B$.
 	%\lstinputlisting{math/ntt.cpp}
 	%\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code
 	\sourcecode{math/transforms/all.cpp}
-	\columnbreak
 	Für sehr viele transforms kann die Vertauschung vorberechnet werden:
 	\sourcecode{math/transforms/fftPerm.cpp}
 	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
 	\sourcecode{math/transforms/fftMul.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
-	\sourcecode{math/simpson.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Numerisch Extremstelle bestimmen}
 	\sourcecode{math/goldenSectionSearch.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Longest Increasing Subsequence}
 	\begin{itemize}
 		\item \code{lower\_bound} $\Rightarrow$ streng monoton
@@ -290,10 +289,6 @@ Multipliziert Polynome $A$ und $B$.
 	\sourcecode{math/longestIncreasingSubsequence.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Inversionszahl}
-	\sourcecode{math/inversions.cpp}
-\end{algorithm}
-
 \begin{algorithm}{\textsc{Legendre}-Symbol}
 	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
 	\begin{align*}
@@ -321,13 +316,17 @@ Multipliziert Polynome $A$ und $B$.
 	\sourcecode{math/legendre.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Inversionszahl}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
+
 \subsection{Satz von \textsc{Sprague-Grundy}}
 Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
 \[
-	g\left(X\right) := \min\left\{
-		\mathbb{Z}_0^+ \setminus
-		\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
-	\right\} 
+g\left(X\right) := \min\left\{
+\mathbb{Z}_0^+ \setminus
+\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
+\right\} 
 \]
 $X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
 Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
@@ -455,7 +454,6 @@ Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Me
 	\end{methods}
 	\sourcecode{math/binomial.cpp}
 
-\columnbreak
 	\begin{methods}
 		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
 	\end{methods}
diff --git a/tcr.pdf b/tcr.pdf
index b3a9efa..2b91879 100644
--- a/tcr.pdf
+++ b/tcr.pdf