moved stuff

8 files changed, 30 insertions, 31 deletions

diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index c58a6e7..f3dc08d 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -27,22 +27,22 @@ struct hp {
 			if (ort == 0) return cross(from, to, a.from) < 0;
 			return cross(b.dir(), a.dir()) * ort > 0;
 		}
-		ll y = cross(a.dir(), b.dir());
-		ll z = cross(b.from - a.from, b.dir());
-		ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
-		// check if i is outside/right of x
-		return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
+		ll x = cross(a.dir(), b.dir());
+		ll y = cross(b.from - a.from, b.dir());
+		ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b
+		// check if i is outside/right of this
+		return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0;
 	}
 };
 
 constexpr ll lim = 2e9+7;
 
 deque<hp> intersect(vector<hp> hps) {
-	hps.push_back(hp(pt{lim+1,-1}));
-	hps.push_back(hp(pt{lim+1,1}));
+	hps.push_back(hp(pt{lim + 1, -1}));
+	hps.push_back(hp(pt{lim + 1, 1}));
 	sort(all(hps));
 
-	deque<hp> dq = {hp(pt{-lim, 1})};
+	deque<hp> dq = {hp(pt{-lim - 1, 1})};
 	for (auto x : hps) {
 		while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
 			dq.pop_back();
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
index c15c25c..ab86f71 100644
--- a/content/math/linearRecurrence.cpp
+++ b/content/math/linearRecurrence.cpp
@@ -10,21 +10,21 @@
 // 	return c;
 // }
 
-ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
 	int n = sz(c);
-	vector<ll> q(n+1, 1);
-	for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod;
+	vector<ll> q(n + 1, 1);
+	for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod;
 	vector<ll> p = mul(f, q);
 	p.resize(n);
 	p.push_back(0);
-	do{
+	do {
 		vector<ll> q2 = q;
-		for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+		for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
 		vector<ll> x = mul(p, q2), y = mul(q, q2);
-		for(int i = 0; i <= n; i++){
+		for (int i = 0; i <= n; i++){
 			p[i] = i == n ? 0 : x[2*i + (k&1)];
 			q[i] = y[2*i];
 		}
-	}while(k /= 2);
+	} while (k /= 2);
 	return p[0];
 }
\ No newline at end of file
diff --git a/content/math/math.tex b/content/math/math.tex
index fb66110..4ac6c9e 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -544,6 +544,11 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 \subsection{Wichtige Zahlen}

 \input{math/tables/composite}

 

+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }

+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}

+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!

+\sourcecode{math/recover.cpp}

+

 \optional{

 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

 \begin{methods}

@@ -552,10 +557,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}

 \end{methods}

 \sourcecode{math/piLehmer.cpp}

-}

 

 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

 \sourcecode{math/piLegendre.cpp}

+}

 

 \begin{algorithm}[optional]{Big Integers}

 	\sourcecode{math/bigint.cpp}

diff --git a/content/other/recover.cpp b/content/math/recover.cpp
index 1a593f0..1a593f0 100644
--- a/content/other/recover.cpp
+++ b/content/math/recover.cpp
diff --git a/content/other/other.tex b/content/other/other.tex
index 368d0b3..191a6da 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -72,6 +72,12 @@
 	\sourcecode{other/sos.cpp}

 \end{algorithm}

 

+\begin{algorithm}{Fast Subset Sum}

+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}

+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.

+	\sourcecode{other/fastSubsetSum.cpp}

+\end{algorithm}

+

 \begin{algorithm}{Parallel Binary Search}

 	\sourcecode{other/pbs.cpp}

 \end{algorithm}

@@ -95,18 +101,6 @@
 	\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}

 \end{algorithm}

 

-\vfill\null\columnbreak

-

-\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }

-\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}

-\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!

-\sourcecode{other/recover.cpp}

-

-\subsection{Fast Subset Sum}

-\method{fastSubsetSum}{findet maximale subset sum $\leq t$}{n \cdot A}

-Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.

-\sourcecode{other/fastSubsetSum.cpp}

-

 \begin{algorithm}[optional]{Zeileneingabe}

 	\sourcecode{other/split.cpp}

 \end{algorithm}

diff --git a/tcr.pdf b/tcr.pdf
index d383dd9..6f156e4 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/test/geometry.h b/test/geometry.h
index 7886fe2..0167d5c 100644
--- a/test/geometry.h
+++ b/test/geometry.h
@@ -1,6 +1,6 @@
-#include <geometry/sortAround.cpp>
-
 namespace details {
+	#include <geometry/sortAround.cpp>
+
 	// Liegt p auf der Strecke a-b?
 	bool pointInLineSegment(pt a, pt b, pt p) {
 		if (cross(a, b, p) != 0) return false;
@@ -59,7 +59,7 @@ namespace Random {
 			for (size_t i = 0; i < dirs.size(); i++) {
 				dirs[i] = pt(x[i], y[i]);
 			}
-			sortAround(0, dirs);
+			details::sortAround(0, dirs);
 
 			vector<pt> res = {{0, 0}};
 			ll maxX = 0;
diff --git a/test/other/recover.cpp b/test/math/recover.cpp
index 72853e5..72853e5 100644
--- a/test/other/recover.cpp
+++ b/test/math/recover.cpp