diff options
| -rw-r--r-- | geometry/geometry.tex | 2 | ||||
| -rw-r--r-- | geometry/polygon.cpp | 40 | ||||
| -rw-r--r-- | math/math.tex | 26 | ||||
| -rw-r--r-- | tcr.pdf | bin | 641186 -> 641935 bytes |
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} Binary files differ |