ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1369. Cockroach Race

tests generator
Posted by LeTim 20 Mar 2025 11:52
Here is a simple "bad" tests generator on C++ to test your solutions (through comparing answers with brutforce solution):

const double PI = 3.14159265358979323846;
mt19937 rnd;

struct Point {
    double x, y;
};

double dist(const Point& a, const Point& b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool check(const vector<Point>& points, const Point& p) {
    for (const auto& p2 : points)
        if (dist(p, p2) < 1e-3)
            return 0;
    return 1;
}

pair<vector<Point>, vector<Point>> gen_bad_test(int m = 100000, int n = 10000, double R = 10000, double r = 10) {
    vector<Point> cockroaches, sweets;
    cockroaches.reserve(m);
    sweets.reserve(n);
    while (m--) {
        Point p;
        do {
            double a = uniform_real_distribution<double>(0, 2*PI)(rnd);
            p = {cos(a) * R, sin(a) * R};
        } while (!check(cockroaches, p));
        cockroaches.emplace_back(p);
    }
    while (n--) {
        Point p;
        do {
            double a = uniform_real_distribution<double>(0, 2*PI)(rnd);
            double d = sqrt(uniform_real_distribution<double>(0, 1)(rnd)) * r;
            p = {cos(a) * d, sin(a) * d};
        } while (!check(cockroaches, p));
        sweets.emplace_back(p);
    }
    return {cockroaches, sweets};
}

This generator uniformly distributes points-cockroaches on a circle of radius R and points-sweets inside a circle of radius r.

And another generator that just distributes all points within [-MAX; MAX] along both axes:

pair<vector<Point>, vector<Point>> gen_rand_test(int m = 100000, int n = 10000, double MAX = 10000) {
    vector<Point> cockroaches, sweets;
    cockroaches.reserve(m);
    sweets.reserve(n);
    auto urd = uniform_real_distribution<double>(-MAX, MAX);
    while (m--) {
        Point p;
        do p.x = urd(rnd), p.y = urd(rnd);
        while (!check(cockroaches, p));
        cockroaches.emplace_back(p);
    }
    while (n--) {
        Point p;
        do p.x = urd(rnd), p.y = urd(rnd);
        while (!check(sweets, p));
        sweets.emplace_back(p);
    }
    return {cockroaches, sweets};
}

I just got AC for this problem and these two generators greatly helped me debug the solution revealing bugs and precision issues