diff options
Diffstat (limited to 'test/geometry.h')
| -rw-r--r-- | test/geometry.h | 140 |
1 files changed, 140 insertions, 0 deletions
diff --git a/test/geometry.h b/test/geometry.h new file mode 100644 index 0000000..7886fe2 --- /dev/null +++ b/test/geometry.h @@ -0,0 +1,140 @@ +#include <geometry/sortAround.cpp> + +namespace details { + // Liegt p auf der Strecke a-b? + bool pointInLineSegment(pt a, pt b, pt p) { + if (cross(a, b, p) != 0) return false; + auto dist = norm(a - b); + return norm(a - p) < dist && norm(b - p) < dist; + } + + // Test auf Streckenschnitt zwischen a-b und c-d. + // (nur intern) + bool lineSegmentIntersection(pt a, pt b, pt c, pt d) { + if (cross(a, b, c) == 0 && cross(a, b, d) == 0) { + return pointInLineSegment(a,b,c) || + pointInLineSegment(a,b,d) || + pointInLineSegment(c,d,a) || + pointInLineSegment(c,d,b); + } + return ccw(a, b, c) * ccw(a, b, d) < 0 && + ccw(c, d, a) * ccw(c, d, b) < 0; + } +} + +namespace Random { + vector<ll> partition(ll n, std::size_t k){//min = 0; + n += k; + vector<ll> res = Random::distinct<ll>(k-1, 1, n); + sort(all(res)); + res.emplace_back(n); + ll last = 0; + for (std::size_t i = 0; i < k; i++) { + res[i] -= last; + last += res[i]; + res[i]--; + } + return res; + } + + vector<pt> convex(int n, ll dim) { + binomial_distribution<int> binomial(n - 2, 0.5); + + while (true) { + int left = 1 + binomial(Random::rng); + int down = 1 + binomial(Random::rng); + auto x = Random::partition(2 * dim - 2, left); + auto y = Random::partition(2 * dim - 2, down); + for (auto& z : x) z = -z; + for (auto& z : y) z = -z; + for (auto z : Random::partition(2 * dim - 2, n - left)) x.push_back(z); + for (auto z : Random::partition(2 * dim - 2, n - down)) y.push_back(z); + auto itX = std::partition(x.begin(), x.end(), [](ll z){return z == 0;}); + auto itY = std::partition(y.begin(), y.end(), [](ll z){return z != 0;}); + if (distance(x.begin(), itX) + distance(itY, y.end()) > n) continue; + shuffle(itX, x.end(), Random::rng); + if (itX != x.begin()) shuffle(y.begin(), itY, Random::rng); + + vector<pt> dirs(n); + for (size_t i = 0; i < dirs.size(); i++) { + dirs[i] = pt(x[i], y[i]); + } + sortAround(0, dirs); + + vector<pt> res = {{0, 0}}; + ll maxX = 0; + ll maxY = 0; + for (auto dir : dirs) { + pt tmp(real(res.back()) + real(dir), + imag(res.back()) + imag(dir)); + maxX = std::max<ll>(maxX, real(tmp)); + maxY = std::max<ll>(maxY, imag(tmp)); + res.emplace_back(tmp); + } + res.pop_back(); + for (auto& point : res) { + point = pt(real(point) + dim - 1 - maxX, + imag(point) + dim - 1 - maxY); + } + bool strict = true; + for (int i = 0; i < n; i++) strict &= cross(res[i], res[(i + 1) % n], res[(i + 2) % n]) != 0; + if (strict) return res; + } + } + + vector<pt> polygon(int n, ll dim) { + while (true) { + vector<pt> ps = points<pt::value_type>(n, -dim, dim); + bool coolinear = false; + for (int i = 0; i < n; i++) { + for (int j = 0; j < i; j++) { + for (int k = 0; k < j; k++) { + coolinear |= cross(ps[i], ps[j], ps[k]) == 0; + } + } + } + if (coolinear) continue; + + bool changed; + do { + changed = false; + for (int i = 0; i < n && !changed; i++) { + for (int j = i + 1; j < n && !changed; j++) { + if (details::lineSegmentIntersection(ps[i], ps[(i+1) % n], ps[j], ps[(j+1) % n])) { + reverse(ps.begin() + i + 1, ps.begin() + j + 1); + changed = true; + } + } + } + } while (changed); + return ps; + } + } + + pt integerPoint(ll range) { + return pt(integer<ll>(-range, range), + integer<ll>(-range, range)); + } + + vector<pt> integerPoints(std::size_t n, ll range) { + vector<pt> res(n); + for (auto& p : res) p = integerPoint(range); + return res; + } + + array<pt, 2> line(ll range) { + pt a = integerPoint(range); + pt b = a; + while (b == a) b = integerPoint(range); + return {a, b}; + } + + array<pt, 3> triangle(ll range) { + pt a = integerPoint(range); + pt b = a; + while (b == a) b = integerPoint(range); + pt c = a; + while (ccw(a, b, c) == 0) c = integerPoint(range); + return {a, b, c}; + } +}
\ No newline at end of file |