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
