From 7a5ef4fbba242e74a1c20f250972518483532172 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 12:21:41 +0100 Subject: Dokument gebaut --- tcr.pdf | Bin 170218 -> 291824 bytes 1 file changed, 0 insertions(+), 0 deletions(-) (limited to 'tcr.pdf') diff --git a/tcr.pdf b/tcr.pdf index 07e4ceb..8a59d24 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 9fe234e7181b1cad9652655e674e7f9f821814b7 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 12:50:19 +0100 Subject: Artikulationpunkte --- graph/articulationPoints.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++ graph/graph.tex | 3 +++ math/math.tex | 7 +++---- tcr.pdf | Bin 291824 -> 297317 bytes 4 files changed, 53 insertions(+), 4 deletions(-) create mode 100644 graph/articulationPoints.cpp (limited to 'tcr.pdf') diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp new file mode 100644 index 0000000..b99a286 --- /dev/null +++ b/graph/articulationPoints.cpp @@ -0,0 +1,47 @@ +vector< vector > adjlist; +vector low; +vector d; +vector isArtPoint; +vector< vector > bridges; //nur fuer Bruecken +int counter = 0; + +void visit(int v, int parent) { + d[v] = low[v] = ++counter; + int numVisits = 0, maxlow = 0; + + for (vector::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) { + if (d[*vit] == 0) { + numVisits++; + visit(*vit, v); + if (low[*vit] > maxlow) { + maxlow = low[*vit]; + } + + if (low[*vit] > d[v]) { //nur fuer Bruecken + bridges[v].push_back(*vit); bridges[*vit].push_back(v); + } + + low[v] = min(low[v], low[*vit]); + } else { + if (d[*vit] < low[v]) { + low[v] = d[*vit]; + } + } + } + + if (parent == -1) { + if (numVisits > 1) isArtPoint[v] = true; + } else { + if (maxlow >= d[v]) isArtPoint[v] = true; + } +} + +void findArticulationPoints() { + low.clear(); low.resize(adjlist.size()); + d.clear(); d.assign(adjlist.size(), 0); + isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false); + bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken + for (int v = 0; v < (int)adjlist.size(); v++) { + if (d[v] == 0) visit(v, -1); + } +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 2bf395c..5fc725e 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,5 +13,8 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} +\subsection{Artikulationspunkte und Brücken} +\lstinputlisting{graph/articulationPoints.cpp} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/math/math.tex b/math/math.tex index 71e5648..973103a 100644 --- a/math/math.tex +++ b/math/math.tex @@ -17,10 +17,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{description} \lstinputlisting{math/multInv.cpp} - -\subsubsection{Primzahlsieb von Eratosthenes} -\lstinputlisting{math/primeSieve.cpp} - \subsubsection{Faktorisierung} \lstinputlisting{math/factor.cpp} @@ -32,3 +28,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp} + +\subsection{Primzahlsieb von Eratosthenes} +\lstinputlisting{math/primeSieve.cpp} diff --git a/tcr.pdf b/tcr.pdf index 8a59d24..c4e7d62 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From f1b3e645381d9b8ea8197fb1473f115de2ee8f96 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 13:03:04 +0100 Subject: adding string chapter --- datastructures/trie.cpp | 25 ------------------------- sonstiges/LCSub.cpp | 26 -------------------------- sonstiges/SufixArray.cpp | 36 ------------------------------------ string/LCSubstring.cpp | 26 ++++++++++++++++++++++++++ string/string.tex | 13 +++++++++++++ string/suffixArray.cpp | 36 ++++++++++++++++++++++++++++++++++++ string/trie.cpp | 25 +++++++++++++++++++++++++ tcr.pdf | Bin 297317 -> 306669 bytes tcr.tex | 1 + 9 files changed, 101 insertions(+), 87 deletions(-) delete mode 100644 datastructures/trie.cpp delete mode 100644 sonstiges/LCSub.cpp delete mode 100644 sonstiges/SufixArray.cpp create mode 100644 string/LCSubstring.cpp create mode 100644 string/string.tex create mode 100644 string/suffixArray.cpp create mode 100644 string/trie.cpp (limited to 'tcr.pdf') diff --git a/datastructures/trie.cpp b/datastructures/trie.cpp deleted file mode 100644 index 9cfcda5..0000000 --- a/datastructures/trie.cpp +++ /dev/null @@ -1,25 +0,0 @@ -//nur für kleinbuchstaben! -struct node { - node *(e)[26]; - int c = 0;//anzahl der wörter die an dem node enden. - node() { for(int i = 0; i < 26; i++) e[i] = NULL; } -}; - -void insert(node *root, string *txt, int s) { - if(s >= txt->length()) root->c++; - else { - int idx = (int)((*txt).at(s) - 'a'); - if(root->e[idx] == NULL) { - root->e[idx] = new node(); - } - insert(root->e[idx], txt, s+1); - } -} - -int contains(node *root, string *txt, int s) { - if(s >= txt->length()) return root->c; - int idx = (int)((*txt).at(s) - 'a'); - if(root->e[idx] != NULL) { - return contains(root->e[idx], txt, s+1); - } else return 0; -} diff --git a/sonstiges/LCSub.cpp b/sonstiges/LCSub.cpp deleted file mode 100644 index 69d636f..0000000 --- a/sonstiges/LCSub.cpp +++ /dev/null @@ -1,26 +0,0 @@ -//longest common substring. -struct lcse { - int i = 0, s = 0; -}; -string lcp(string s[2]) { - if(s[0].length() == 0 || s[1].length() == 0) return ""; - vector a(s[0].length()+s[1].length()); - for(int k = 0; k < a.size(); k++) a[k].i=(k < s[0].length() ? k : k - s[0].length()), a[k].s = (k < s[0].length() ? 0 : 1); - sort(a.begin(), a.end(), [&] (const lcse &u, const lcse &l) { - int ui = u.i, li = l.i; - while(ui < s[u.s].length() && li < s[l.s].length()) { - if(s[u.s][ui] < s[l.s][li]) return true; - else if(s[u.s][ui] > s[l.s][li]) return false; - ui++; li++; - } - return !(ui < s[u.s].length()); - }); - int r = 0, m=0, c=0; - for(int i = 0; i < a.size() - 1; i++) { - if(a[i].s == a[i+1].s) continue; - c = 0; - while(a[i].i+c < s[a[i].s].length() && a[i+1].i+c < s[a[i+1].s].length() && s[a[i].s][a[i].i+c] == s[a[i+1].s][a[i+1].i+c]) c++; - if(c > m) r=i, m=c; - } - return m == 0 ? "" : s[a[r].s].substr(a[r].i, m); -} diff --git a/sonstiges/SufixArray.cpp b/sonstiges/SufixArray.cpp deleted file mode 100644 index bb742f6..0000000 --- a/sonstiges/SufixArray.cpp +++ /dev/null @@ -1,36 +0,0 @@ -//longest common substring in one string (overlapping not excluded) -//contains suffix array:--------------------------------------------------------------------------------------------------------- -int cmp(string &s,vector> &v, vector &a, int i, int vi, int u, int l) { - int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; - if(i == 1) return s[u] - s[l]; - else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]); - else { //beide größer tifft nicht mehr ein, da ansonsten vorher schon unterschied in länge - if(u2 >= s.length()) return -1; - else if(l2 >= s.length()) return 1; - else return v[vi2][u2] - v[vi2][l2]; - } -} - -string lcsub(string s) { - if(s.length() == 0) return ""; - vector a(s.length()); - vector> v(2, vector(s.length(), 0)); - int vi = 0; - for(int k = 0; k < a.size(); k++) a[k] = k; - for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { - sort(a.begin(), a.end(), [&] (const int &u, const int &l) { - return cmp(s, v, a, i, vi, u, l) < 0; - }); - v[vi][a[0]] = 0; - for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, a, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); - } -//------------------------------------------------------------------------------------------------------------------------------- - int r = 0, m=0, c=0; - for(int i = 0; i < a.size() - 1; i++) { - c = 0; - while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; - if(c > m) r=i, m=c; - } - return m == 0 ? "" : s.substr(a[r], m); -} - diff --git a/string/LCSubstring.cpp b/string/LCSubstring.cpp new file mode 100644 index 0000000..69d636f --- /dev/null +++ b/string/LCSubstring.cpp @@ -0,0 +1,26 @@ +//longest common substring. +struct lcse { + int i = 0, s = 0; +}; +string lcp(string s[2]) { + if(s[0].length() == 0 || s[1].length() == 0) return ""; + vector a(s[0].length()+s[1].length()); + for(int k = 0; k < a.size(); k++) a[k].i=(k < s[0].length() ? k : k - s[0].length()), a[k].s = (k < s[0].length() ? 0 : 1); + sort(a.begin(), a.end(), [&] (const lcse &u, const lcse &l) { + int ui = u.i, li = l.i; + while(ui < s[u.s].length() && li < s[l.s].length()) { + if(s[u.s][ui] < s[l.s][li]) return true; + else if(s[u.s][ui] > s[l.s][li]) return false; + ui++; li++; + } + return !(ui < s[u.s].length()); + }); + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + if(a[i].s == a[i+1].s) continue; + c = 0; + while(a[i].i+c < s[a[i].s].length() && a[i+1].i+c < s[a[i+1].s].length() && s[a[i].s][a[i].i+c] == s[a[i+1].s][a[i+1].i+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s[a[r].s].substr(a[r].i, m); +} diff --git a/string/string.tex b/string/string.tex new file mode 100644 index 0000000..1335c4a --- /dev/null +++ b/string/string.tex @@ -0,0 +1,13 @@ +\section{Strings} + +\subsection{\textsc{Knuth-Morris-Pratt}-Algorithmus} +\lstinputlisting{string/kmp.cpp} + +\subsection{Trie} +\lstinputlisting{string/trie.cpp} + +\subsection{Suffix-Array} +\lstinputlisting{string/suffixArray.cpp} + +\subsection{Longest Common Substring} +\lstinputlisting{string/LCSubstring.cpp} diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp new file mode 100644 index 0000000..2b2a87b --- /dev/null +++ b/string/suffixArray.cpp @@ -0,0 +1,36 @@ +//longest common substring in one string (overlapping not excluded) +//contains suffix array:-------------------------------------------------------------------- +int cmp(string &s,vector> &v, vector &a, int i, int vi, int u, int l) { + int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; + if(i == 1) return s[u] - s[l]; + else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]); + else { //beide groesser tifft nicht mehr ein, da ansonsten vorher schon unterschied in Laenge + if(u2 >= s.length()) return -1; + else if(l2 >= s.length()) return 1; + else return v[vi2][u2] - v[vi2][l2]; + } +} + +string lcsub(string s) { + if(s.length() == 0) return ""; + vector a(s.length()); + vector> v(2, vector(s.length(), 0)); + int vi = 0; + for(int k = 0; k < a.size(); k++) a[k] = k; + for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { + sort(a.begin(), a.end(), [&] (const int &u, const int &l) { + return cmp(s, v, a, i, vi, u, l) < 0; + }); + v[vi][a[0]] = 0; + for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, a, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); + } +//------------------------------------------------------------------------------------------- + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + c = 0; + while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s.substr(a[r], m); +} + diff --git a/string/trie.cpp b/string/trie.cpp new file mode 100644 index 0000000..f4b979c --- /dev/null +++ b/string/trie.cpp @@ -0,0 +1,25 @@ +//nur fuer kleinbuchstaben! +struct node { + node *(e)[26]; + int c = 0;//anzahl der woerter die an dem node enden. + node() { for(int i = 0; i < 26; i++) e[i] = NULL; } +}; + +void insert(node *root, string *txt, int s) { + if(s >= txt->length()) root->c++; + else { + int idx = (int)((*txt).at(s) - 'a'); + if(root->e[idx] == NULL) { + root->e[idx] = new node(); + } + insert(root->e[idx], txt, s+1); + } +} + +int contains(node *root, string *txt, int s) { + if(s >= txt->length()) return root->c; + int idx = (int)((*txt).at(s) - 'a'); + if(root->e[idx] != NULL) { + return contains(root->e[idx], txt, s+1); + } else return 0; +} diff --git a/tcr.pdf b/tcr.pdf index c4e7d62..345a1a7 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 4dce95e..4328b73 100644 --- a/tcr.tex +++ b/tcr.tex @@ -56,6 +56,7 @@ \input{graph/graph} \input{geometry/geometry} \input{math/math} +\input{string/string} \input{sonstiges/sonstiges} \end{document} \ No newline at end of file -- cgit v1.2.3 From 0bdabf851fd4a83e57fced5864aa85af7029ad48 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 16:59:45 +0100 Subject: Dokument gebaut --- graph/graph.tex | 7 +++++++ tcr.pdf | Bin 306669 -> 313827 bytes tcr.tex | 1 + 3 files changed, 8 insertions(+) (limited to 'tcr.pdf') diff --git a/graph/graph.tex b/graph/graph.tex index 5fc725e..5982e5a 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -16,5 +16,12 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Artikulationspunkte und Brücken} \lstinputlisting{graph/articulationPoints.cpp} +\subsection{Eulertouren} +\begin{itemize} + \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). + \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). + \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} +\end{itemize} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index 345a1a7..eec39ab 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 4328b73..3e6a0ed 100644 --- a/tcr.tex +++ b/tcr.tex @@ -8,6 +8,7 @@ \usepackage{amssymb} \usepackage{enumitem} +\setlist{nosep} \usepackage{color} \definecolor{darkred}{rgb}{0.72,0.07,0.07} -- cgit v1.2.3 From 4663f02b5df9713ce2d75b4f19bc6ca103f2d0ce Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 17:10:04 +0100 Subject: eulerzyklen --- graph/euler.cpp | 41 +++++++++++++++++++++++++++++++++++++++++ graph/graph.tex | 2 ++ tcr.pdf | Bin 313827 -> 313603 bytes tcr.tex | 7 ++++++- 4 files changed, 49 insertions(+), 1 deletion(-) create mode 100644 graph/euler.cpp (limited to 'tcr.pdf') diff --git a/graph/euler.cpp b/graph/euler.cpp new file mode 100644 index 0000000..74b3399 --- /dev/null +++ b/graph/euler.cpp @@ -0,0 +1,41 @@ +vector< vector > adjlist; +vector< vector > otherIdx; +vector cycle; +vector validIdx; + +void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n. + int neighA = adjlist[n][a]; + int neighB = adjlist[n][b]; + int idxNeighA = otherIdx[n][a]; + int idxNeighB = otherIdx[n][b]; + swap(adjlist[n][a], adjlist[n][b]); + swap(otherIdx[n][a], otherIdx[n][b]); + otherIdx[neighA][idxNeighA] = b; + otherIdx[neighB][idxNeighB] = a; +} + +void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante). + int other = adjlist[n][i]; + if (other == n) { //Schlingen + validIdx[n]++; + return; + } + int otherIndex = otherIdx[n][i]; + validIdx[n]++; + if (otherIndex != validIdx[other]) { + swapEdges(other, otherIndex, validIdx[other]); + } + validIdx[other]++; +} + +//findet Eulerzyklus an Knoten n startend +//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok) +//teste vorher, ob Eulerzyklus ueberhaupt existiert! +void euler(int n) { + while (validIdx[n] < (int)adjlist[n].size()) { + int nn = adjlist[n][validIdx[n]]; + removeEdge(n, validIdx[n]); + euler(nn); + } + cycle.push_back(n); //Zyklus am Ende in cycle +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 5982e5a..fada803 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -21,7 +21,9 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} + \item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher. \end{itemize} +\lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index eec39ab..c735878 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 3e6a0ed..cea7d08 100644 --- a/tcr.tex +++ b/tcr.tex @@ -44,13 +44,18 @@ \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry} +\usepackage{multicol} + \title{Team Contest Reference} \author{ChaosKITs \\ Karlsruhe Institute of Technology} \begin{document} \maketitle -\tableofcontents +\setlength{\columnsep}{1cm} +\begin{multicols}{2} + \tableofcontents +\end{multicols} \newpage \input{datastructures/datastructures} -- cgit v1.2.3 From 597fd2a7cf8b39c49c890e836102d1c7ab582e99 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 17:51:22 +0100 Subject: bisschen mehr Geometrie --- geometry/formulars.cpp | 27 ++++++++++++++++++++++++++- tcr.pdf | Bin 313603 -> 315778 bytes 2 files changed, 26 insertions(+), 1 deletion(-) (limited to 'tcr.pdf') diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp index 6984be9..5369b50 100644 --- a/geometry/formulars.cpp +++ b/geometry/formulars.cpp @@ -55,4 +55,29 @@ bool pointOnLine(pt a, pt b, pt p) { //testet, ob d in der gleichen Ebene liegt wie a, b, und c bool isCoplanar(pt a, pt b, pt c, pt d) { return (b - a) * (c - a) * (d - a) == 0; -} \ No newline at end of file +} +//berechnet den Flaecheninhalt eines Polygons (nicht selbstschneidend) +double areaOfPolygon(vector &polygon) { //jeder Eckpunkt nur einmal im Vektor + double res = 0; int n = polygon.size(); + for (int i = 0; i < (int)polygon.size(); i++) + res += real(polygon[i]) * imag(polygon[(i + 1) % n]) - real(polygon[(i + 1) % n]) * imag(polygon[i]); + return 0.5 * abs(res); +} +//testet, ob sich zwei Rechtecke (p1, p2) und (p3, p4) schneiden (jeweils gegenueberliegende Ecken) +bool rectIntersection(pt p1, pt p2, pt p3, pt p4) { + double minx12 = min(real(p1), real(p2)), maxx12 = max(real(p1), real(p2)); + double minx34 = min(real(p3), real(p4)), maxx34 = max(real(p3), real(p4)); + double miny12 = min(imag(p1), imag(p2)), maxy12 = max(imag(p1), imag(p2)); + double miny34 = min(imag(p3), imag(p4)), maxy34 = max(imag(p3), imag(p4)); + return (maxx12 >= minx34) && (maxx34 >= minx12) && (maxy12 >= miny34) && (maxy34 >= miny12); +} +//testet, ob ein Punkt im Polygon liegt (beliebige Polygone) +bool pointInPolygon(pt p, vector &polygon) { //jeder Eckpunkt nur einmal im Vektor + pt rayEnd = p + pt(1, 1000000); + int counter = 0, n = polygon.size(); + for (int i = 0; i < n; i++) { + pt start = polygon[i], end = polygon[(i + 1) % n]; + if (lineSegmentIntersection(p, rayEnd, start, end)) counter++; + } + return counter & 1; +} diff --git a/tcr.pdf b/tcr.pdf index c735878..e16a3dd 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3