|
|
back to boardtests 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 |
|
|