|  | 
|  | 
| back to board | tests generator Posted by LeTim  20 Mar 2025 11:52Here 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
 | 
 | 
|