1#ifndef JNGEN_INCLUDE_GEOMETRY_INL_H2#error File "geometry_inl.h" must not be included directly.3#include "../geometry.h" // for completion engine4#endif56namespace jngen {78Point GeometryRandom::point(long long C) {9    return point(0, 0, C, C);10}1112Point GeometryRandom::point(long long min, long long max) {13    return point(min, min, max, max);14}1516Point GeometryRandom::point(17        long long X1, long long Y1,18        long long X2, long long Y2) {19    long long x = rnd.tnext<long long>(X1, X2);20    long long y = rnd.tnext<long long>(Y1, Y2);21    return Point(x, y);22}2324Point GeometryRandom::pointf(long double C) {25    return pointf(0, 0, C, C);26}2728Point GeometryRandom::pointf(long double min, long double max) {29    return pointf(min, min, max, max);30}3132Point GeometryRandom::pointf(33        long double X1, long double Y1,34        long double X2, long double Y2)35{36    long double x = rnd.tnext<long double>(X1, X2);37    long double y = rnd.tnext<long double>(Y1, Y2);38    return Pointf(x, y);39}404142Polygon GeometryRandom::convexPolygon(int n, long long C) {43    return convexPolygon(n, 0, 0, C, C);44}4546Polygon GeometryRandom::convexPolygon(int n, long long min, long long max) {47    return convexPolygon(n, min, min, max, max);48}4950Polygon GeometryRandom::convexPolygon(51            int n,52            long long X1, long long Y1,53            long long X2, long long Y2)54{55    // todo: off-by-one error?56    auto dx = X2 - X1;57    auto dy = Y2 - Y1;58    ensure(n >= 0);59    Polygon res = detail::convexPolygonByEllipse<long long>(60        n * 10, // BUBEN!61        Point(dx / 2, dy / 2),62        Point(dx / 2, 0),63        Point(0, dy / 2)64    );65    res.shift(Point(X1, Y1));66    for (auto& x: res) {67        ENSURE(x.x >= X1);68        ENSURE(x.x <= X2);69        ENSURE(x.y >= Y1);70        ENSURE(x.y <= Y2);71    }7273    ensure(74        static_cast<int>(res.size()) >= n,75        "Cannot generate a convex polygon with so many vertices");7677    return res.subseq(Array::id(res.size()).choice(n).sort());78}798081TArray<Point> GeometryRandom::pointsInGeneralPosition(int n, long long C) {82    return pointsInGeneralPosition(n, 0, 0, C, C);83}8485TArray<Point> GeometryRandom::pointsInGeneralPosition(86        int n, long long min, long long max)87{88    return pointsInGeneralPosition(n, min, min, max, max);89}9091TArray<Point> GeometryRandom::pointsInGeneralPosition(92        int n,93        long long X1, long long Y1,94        long long X2, long long Y2)95{96    struct Line {97        long long A, B, C; // Ax + By + C = 098        Line() {}99        Line(const Point& p1, const Point& p2) {100            A = p1.y - p2.y;101            B = p2.x - p1.x;102            C = -(p1.x * A + p1.y * B);103104            ENSURE(A != 0 || B != 0);105106            long long g = util::gcd(A, util::gcd(B, C));107            A /= g;108            B /= g;109            C /= g;110            if (A < 0 || (A == 0 && B < 0)) {111                A = -A;112                B = -B;113                C = -C;114            }115        }116117        bool operator<(const Line& other) const {118            return std::tie(A, B, C) < std::tie(other.A, other.B, other.C);119        }120    };121122    const long long LIMIT = 2e9;123    ensure(124        std::abs(X2 - X1) <= LIMIT && X1 <= LIMIT && X2 <= LIMIT &&125            std::abs(Y2 - Y1) <= LIMIT && Y1 <= LIMIT && Y2 <= LIMIT,126        "rndg.pointsInGeneralPosition must not be called with coordinates "127        "larger than 2e9");128129    std::set<Line> lines;130    std::unordered_set<Point> points;131132    TArray<Point> res;133134    while (static_cast<int>(res.size()) != n) {135        Point p = point(X1, Y1, X2, Y2);136137        if (points.count(p)) {138            continue;139        }140141        if (std::none_of(142                res.begin(),143                res.end(),144                [&lines, &p] (const Point& q) {145                    return lines.count(Line(p, q));146                }))147        {148            points.insert(p);149            for (const auto& q: res) {150                lines.emplace(p, q);151            }152            res.push_back(p);153        }154    }155    return res;156}157158} // namespace jngen