ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1369. Тараканьи бега

tests generator
Послано LeTim 20 мар 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