summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--content/datastructures/dynamicConvexHull.cpp16
-rw-r--r--content/datastructures/pbds.cpp4
-rw-r--r--content/geometry/convexHull.cpp4
-rw-r--r--content/geometry/hpi.cpp2
-rw-r--r--content/graph/bitonicTSP.cpp2
-rw-r--r--content/graph/bitonicTSPsimple.cpp2
-rw-r--r--content/graph/pushRelabel.cpp2
-rw-r--r--tcr.pdfbin691284 -> 691101 bytes
-rw-r--r--test/datastructures/fenwickTree2.cpp2
-rw-r--r--test/geometry/delaunay.cpp6
-rw-r--r--test/math/gauss.cpp2
-rw-r--r--test/math/inversionsMerge.cpp2
12 files changed, 22 insertions, 22 deletions
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 27ec898..abae1d7 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,22 +1,22 @@
struct Line {
- mutable ll m, b, p;
+ mutable ll m, c, p;
bool operator<(const Line& o) const {return m < o.m;}
bool operator<(ll x) const {return p < x;}
};
struct HullDynamic : multiset<Line, less<>> { // max über Geraden
- // (for doubles, use INF = 1/.0, div(a,b) = a/b)
- ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
+ // (for doubles, use INF = 1/.0, div(a,c) = a/c)
+ ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);}
bool isect(iterator x, iterator y) {
if (y == end()) {x->p = INF; return false;}
- if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
- else x->p = div(y->b - x->b, x->m - y->m);
+ if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+ else x->p = div(y->c - x->c, x->m - y->m);
return x->p >= y->p;
}
- void add(ll m, ll b) {
- auto x = insert({m, b, 0});
+ void add(ll m, ll c) {
+ auto x = insert({m, c, 0});
while (isect(x, next(x))) erase(next(x));
if (x != begin()) {
x--;
@@ -31,6 +31,6 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden
ll query(ll x) {
auto l = *lower_bound(x);
- return l.m * x + l.b;
+ return l.m * x + l.c;
}
};
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index f0889a2..de0ace6 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -6,11 +6,11 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
// T.order_of_key(x): number of elements strictly less than x
// *T.find_by_order(k): k-th element
+constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
template<typename T>
struct chash {
- static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
size_t operator()(T o) const {
- return __builtin_bswap64(hash<T>()(o) * C);
+ return __builtin_bswap64(hash<T>()(o) * RNG);
}};
template<typename K, typename V>
using hashMap = gp_hash_table<K, V, chash<K>>;
diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp
index 6d89e05..1173924 100644
--- a/content/geometry/convexHull.cpp
+++ b/content/geometry/convexHull.cpp
@@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){
while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--;
h[k++] = *it;
}};
- half(all(pts), 1);// Untere Hülle.
- half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+ half(all(pts), 1); // Untere Hülle.
+ half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
h.resize(k);
return h;
}
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index bd3ab1e..c58a6e7 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP
bool left(pt p) {return real(p) < 0 ||
(real(p) == 0 && imag(p) < 0);}
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
(lt.back() == 1 ? lt : ut).push_back(0);
reverse(all(lt));
lt.insert(lt.end(), all(ut));
- return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+ return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
}
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
rl.push_back(v); p2 = v;
}}
lr.insert(lr.end(), rl.rbegin(), rl.rend());
- return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+ return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
}
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
cur.assign(n, 0);
H.assign(n, 0);
H[s] = n;
- ec[t] = 1;//never set t to active...
+ ec[t] = 1; //never set t to active...
vector<int> co(2*n);
co[0] = n - 1;
for (Edge& e : adj[s]) addFlow(e, e.c);
diff --git a/tcr.pdf b/tcr.pdf
index b096438..57691c5 100644
--- a/tcr.pdf
+++ b/tcr.pdf
Binary files differ
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index aa99576..89d5b0f 100644
--- a/test/datastructures/fenwickTree2.cpp
+++ b/test/datastructures/fenwickTree2.cpp
@@ -9,7 +9,7 @@ void stress_test() {
ll queries = 0;
for (int tries = 0; tries < 100; tries++) {
int n = Random::integer<int>(10, 100);
- vector<ll> naive(n);// = Random::integers<ll>(n, -1000, 1000);
+ vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
init(naive);
for (int operations = 0; operations < 1000; operations++) {
{
diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp
index 7f8ec30..5740b95 100644
--- a/test/geometry/delaunay.cpp
+++ b/test/geometry/delaunay.cpp
@@ -16,11 +16,11 @@ vector<pt> convexHull(vector<pt> pts){
vector<pt> h(2 * sz(pts));
auto half = [&](auto begin, auto end, int t) {
for (auto it = begin; it != end; it++) {
- while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points!
+ while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points!
h[k++] = *it;
}};
- half(all(pts), 1);// Untere Hülle.
- half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+ half(all(pts), 1); // Untere Hülle.
+ half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
h.resize(k);
return h;
}
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
index 37bacce..6e4759d 100644
--- a/test/math/gauss.cpp
+++ b/test/math/gauss.cpp
@@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
mat[i].resize(2*n);
mat[i][n+i] = 1;
}
- gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+ gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs...
vector<vector<double>> res(m);
for (int i = 0; i < n; i++) {
res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
index 85ab0d2..acdc555 100644
--- a/test/math/inversionsMerge.cpp
+++ b/test/math/inversionsMerge.cpp
@@ -16,7 +16,7 @@ void stress_test() {
for (ll i = 0; i < 100'000; i++) {
int n = Random::integer<int>(1, 100);
vector<ll> v(n);
- for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+ for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ):
shuffle(all(v), Random::rng);
ll expected = naive(v);
ll got = mergeSort(v);
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:14:31 +0000