diff options
| -rw-r--r-- | convenience/convenience.tex | 9 | ||||
| -rw-r--r-- | convenience/template.cpp | 10 | ||||
| -rw-r--r-- | math/gcDist.cpp | 23 | ||||
| -rw-r--r-- | math/math.tex | 5 | ||||
| -rw-r--r-- | string/kmp.cpp | 51 | ||||
| -rw-r--r-- | tcr.pdf | bin | 250839 -> 251573 bytes |
6 files changed, 57 insertions, 41 deletions
diff --git a/convenience/convenience.tex b/convenience/convenience.tex index 04964f9..70f9ad9 100644 --- a/convenience/convenience.tex +++ b/convenience/convenience.tex @@ -3,11 +3,11 @@ \subsection{Zeileneingabe} \lstinputlisting{convenience/split.cpp} -\subsection{Template} -\lstinputlisting{convenience/template.cpp} - \subsection{Sonstiges} \begin{lstlisting} +// Alles-Haeder. +#include <bits/stdc++.h> + // Setzt das deutsche Tastaturlayout. setxkbmap de @@ -16,4 +16,7 @@ ios::sync_with_stdio(false); // Set mit eigener Sortierfunktion. Typ muss nicht explizit angegeben werden. set<point2, decltype(comp)> set1(comp); + +// PI +#define PI (2*acos(0)) \end{lstlisting} diff --git a/convenience/template.cpp b/convenience/template.cpp deleted file mode 100644 index f8631ac..0000000 --- a/convenience/template.cpp +++ /dev/null @@ -1,10 +0,0 @@ -#include <bits/stdc++.h> - -using namespace std; - -void solve() {} - -int main() { - solve(); - return 0; -} diff --git a/math/gcDist.cpp b/math/gcDist.cpp new file mode 100644 index 0000000..d661744 --- /dev/null +++ b/math/gcDist.cpp @@ -0,0 +1,23 @@ +// Great Cirlce Distance mit Längen- und Breitengrad. +double gcDist(double pLat, double pLon, double qLat, double qLon, double radius) { + pLat *= PI / 180; pLon *= PI / 180; qLat *= PI / 180; qLon *= PI / 180; + return radius * acos(cos(pLat) * cos(pLon) * cos(qLat) * cos(qLon) + + cos(pLat) * sin(pLon) * cos(qLat) * sin(qLon) + + sin(pLat) * sin(qLat)); +} + +// Great Cirlce Distance mit kartesischen Koordinaten. +double gcDist(point p, point q) { + return acos(p.x * q.x + p.y * q.y + p.z * q.z); +} + +// 3D Punkt in kartesischen Koordinaten. +struct point{ + double x, y, z; + point() {} + point(double x, double y, double z) : x(x), y(y), z(z) {} + point(double lat, double lon) { + lat *= PI / 180.0; lon *= PI / 180.0; + x = cos(lat) * sin(lon); y = cos(lat) * cos(lon); z = sin(lat); + } +}; diff --git a/math/math.tex b/math/math.tex index 51410bd..90e7b3b 100644 --- a/math/math.tex +++ b/math/math.tex @@ -176,4 +176,7 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale \#labeled rooted trees & $n^{n-1}$\\ \#labeled unrooted trees & $n^{n-2}$\\ \hline -\end{tabular}
\ No newline at end of file +\end{tabular} + +\subsection{3D-Kugeln} +\lstinputlisting{math/gcDist.cpp} diff --git a/string/kmp.cpp b/string/kmp.cpp index 6844975..47feac5 100644 --- a/string/kmp.cpp +++ b/string/kmp.cpp @@ -1,30 +1,27 @@ -//Preprocessing Substring sub for KMP-Search -vector<int> kmp_preprocessing(string& sub) { - vector<int> b(sub.size() + 1); - b[0] = -1; - int i = 0, j = -1; - while(i < sub.size()) { - while(j >= 0 && sub[i] != sub[j]) - j = b[j]; - i++; j++; - b[i] = j; - } - return b; +// Laufzeit: O(n + m), n = #Text, m = #Pattern +vector<int> kmp_preprocessing(string &sub) { + vector<int> b(sub.length() + 1); + b[0] = -1; + int i = 0, j = -1; + while (i < (int)sub.length()) { + while (j >= 0 && sub[i] != sub[j]) j = b[j]; + i++; j++; + b[i] = j; + } + return b; } -//Searching after Substring sub in s -vector<int> kmp_search(string& s, string& sub) { - vector<int> pre = kmp_preprocessing(sub); - vector<int> result; - int i = 0, j = -1; - while(i < s.size()) { - while(j >= 0 && s[i] != sub[j]) - j = pre[j]; - i++; j++; - if(j == sub.size()) { - result.push_back(i-j); - j = pre[j]; - } - } - return result; +vector<int> kmp_search(string &s, string &sub) { + vector<int> pre = kmp_preprocessing(sub); + vector<int> result; + int i = 0, j = 0; + while (i < (int)s.length()) { + while (j >= 0 && s[i] != sub[j]) j = pre[j]; + i++; j++; + if (j == (int)sub.length()) { + result.push_back(i - j); + j = pre[j]; + } + } + return result; } Binary files differ |