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

If there is a way to improve, let me know:

#ifdef __MINGW32__
#define uputchar _putchar_nolock
#define ugetchar _getchar_nolock
#define ufread _fread_nolock
#define funlock _unlock_file
#else
#define uputchar putchar_unlocked
#define ugetchar getchar_unlocked
#define ufread fread_unlocked
#define funlock funlockfile
#endif

namespace
{

#if 1
struct
{

    int c;
    int operator * () const { return c; }
    auto & operator ++ () { c = ugetchar(); return *this; }
    auto operator ++ (int) { auto prev = *this; operator ++ (); return prev; }

} cursor;
#else
char input[(1 << 21) + (1 << 19)];
auto cursor = input;
auto input_size = cursor - input;
#endif

inline
void skip_ws()
{
    for (;;) {
        switch (*++cursor) {
        case ' ' :
        case '\t' :
        case '\r' :
        case '\n' :
            break;
        default :
            return;
        }
    }
}

inline
void read_input()
{
    //std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
#if 0
#ifdef ONLINE_JUDGE
    cursor += ufread(input, sizeof(char), sizeof input, stdin);
#else
    {
        const char s[] = R"(4
                         0 0
                         1 0
                         0 1
                         1 2
                         2
                         0 0
                         0 2)";
        cursor = std::copy(s, s + sizeof s - 1, cursor);
    }
#endif
    //assert(cursor < input + sizeof input);
    //assert(input + 0 != nullptr);
    input_size = cursor - input;
    cursor = input - 1;
#endif
}

template< typename U >
void read_uint(U & u)
{
    static_assert(std::is_unsigned< U >::value, "!");
    u = 0;
    for (;;)  {
        char c = *cursor;
        if ((c < '0') || ('9' < c)) {
            break;
        }
        ++cursor;
        u = (u * 10) + (c - '0');
    }
}

template< typename I >
void read_int(I & i)
{
    char sign = *cursor;
    switch (sign) {
    case '+' :
    case '-' :
        ++cursor;
    }
    std::make_unsigned_t< I > u = 0;
    for (;;)  {
        char c = *cursor;
        if ((c < '0') || ('9' < c)) {
            break;
        }
        ++cursor;
        u = (u * 10) + (c - '0');
    }
    i = I(u);
    if (sign == '-') {
        i = -i;
    }
}

template< typename F >
void read_float(F & result)
{
    static_assert(std::is_floating_point< F >::value, "!");
    char c = *cursor;
    std::uint8_t significand[std::numeric_limits< F >::digits10];
    auto s = significand;
    std::int32_t after = 0;
    std::int32_t before = 0;
    char sign = c;
    switch (c) {
    case '-' :
    case '+' :
        c = *++cursor;
    }
    [&]
    {
        bool d = false;
        for (;;) {
            switch (c) {
            case '.' :
                before = 1;
                break;
            case '0' ... '9' : {
                if (c != '0') {
                    d = true;
                }
                if (0 < before) {
                    ++before;
                }
                if (d) {
                    *s++ = (c - '0');
                    if (s == significand + sizeof significand) {
                        std::int32_t a = 0;
                        for (;;) {
                            switch ((c = *++cursor)) {
                            case '0' ... '9' :
                                ++a;
                                break;
                            case '.' :
                                after = a;
                                break;
                            default :
                                if ((before == 0) && (after == 0)) {
                                    after = a;
                                }
                                return;
                            }
                        }
                    }
                }
                break;
            }
            default :
                if (!d) {
                    *s++ = 0;
                }
                return;
            }
            c = *++cursor;
        }
    }();
    if (0 < before) {
        after -= (before - 1);
    }
    std::uint32_t exponent = 0;
    switch (c) {
    case 'e' :
    case 'E' : {
        c = *++cursor;
        char esign = c;
        switch (c) {
        case '-' :
        case '+' :
            c = *++cursor;
            break;
        }
        [&]
        {
            for (;;) {
                switch (c) {
                case '0' ... '9' :
                    exponent = (exponent * 10) + (c - '0');
                    break;
                default : {
                    return;
                }
                }
                c = *++cursor;
            }
        }();
        if (esign == '-') {
            after -= exponent;
        } else {
            after += exponent;
        }
    }
    }

    alignas(32) std::uint8_t bcd[10] = {};
    std::uint32_t b = 0;
    do {
        --s;
        if ((b % 2) == 0) {
            bcd[b / 2] = *s;
        } else {
            bcd[b / 2] |= (*s << 4);
        }
        ++b;
    } while (s != significand);

    if (sign == '-') {
        bcd[9] = (1 << 7);
    }

    asm(
    "fldl2t;"
    "fildl %[exp10];"
    "fmulp;"
    "fld %%st;"
    "frndint;"
    "fxch;"
    "fsub %%st(1), %%st;"
    "f2xm1;"
    "fld1;"
    "faddp;"
    "fscale;"
    "fstp %%st(1);"
    "fbld %[tbyte];"
    "fmulp;"
    : "=t"(result)
    : [exp10]"m"(after), [tbyte]"m"(bcd)
    : "st(1)", "st(2)"
    );
}

template< typename I >
void print_int(I value)
{
    if (value == 0) {
        uputchar('0');
        return;
    }
    std::make_unsigned_t< I > v;
    if (value < 0) {
        uputchar('-');
        v = decltype(v)(-value);
    } else {
        v = decltype(v)(value);
    }
    I rev = v;
    I count = 0;
    while ((rev % 10) == 0) {
        ++count;
        rev /= 10;
    }
    rev = 0;
    while (v != 0) {
        rev = (rev * 10) + (v % 10);
        v /= 10;
    }
    while (rev != 0) {
        uputchar("0123456789"[rev % 10]);
        rev /= 10;
    }
    while (0 != count) {
        --count;
        uputchar('0');
    }
}

}

Epsilon to compare squared distances must be exactly 1.0 / (1 << 24) (at least for M*N algo). Even 23 and 25 leads to WA.

Make two separate arrays for x and y coordinates of cockroaches.
Don't use horizontal instructions in tight loops.
Perform all the develop and debug in 32-bit mode (evidently GCC/Clang on server has -m32 key). x86-64 has RIP-relative addressing, there would be bottlneck when you go back to 32-bit build and try to backport from 64-bit one.
First loop for each sweet is straitforward. Don't use `displacement(base,index,scale)` addressing. Always run all over the `base` part. Finally it may give about a couple of hundred ms.
In second loop for each sweet you may use BSF instruction to get least significant bit offset (remeber, judge runs on Sandy Bridge arch). Use LEA to calculate simple index arithmetic. Here is mine:

            size_type R = 0;
            asm
            (
            "vbroadcastsd %[dmin], %%ymm5;"

            "dloop:"
            "vcmpgt_oqpd %[d](,%[i],8), %%ymm5, %%ymm6;"
            "vmovmskpd %%ymm6, %%eax;"
            "test %%eax, %%eax;"
            "jz rnext;"
            "rloop:"
            "bsf %%eax, %%edx;"
            "lea 1(%%edx,%[i]), %%edx;"
            "mov %%edx, %[results](,%[R],4);"
            "inc %[R];"
            "lea -1(%%eax), %%edx;"
            "and %%edx, %%eax;"
            "jnz rloop;"

            "rnext:"
            "add $4, %[i];"
            "cmp %[M], %[i];"
            "jl dloop;"
            : [R]"=b"(R)
            : [d]"m"(d), [dmin]"m"(dmin),
              "0"(R), [results]"m"(results),
              [M]"r"(M), [i]"c"(0)
            : "cc", "memory",
              "%eax", "%edx",
              "%ymm5", "%ymm6"
            );

Custom IO gives about 300+ ms.

I hope M*N solutions finally will loose their ACs someday (at least until hardware will be updated to AVX512-compatible).

There is a restiction for X and Y values: −10000.0 ≤ x, y ≤ 10000.0. Does .0 (sigle zero) means that only one digit after the decimal point is possible? Or if there any restriction for number of digits after the decimal point?

Who had a Wrong Answer in 5 th test ? What mistake may be there ?

Russian: Далее следуют M строк по 2 целых числа в каждой — координаты тараканов в настоящий момент. M + 2 строка содержит число ??? N (0 ≤ N ≤ 10000) ??? . Далее N строк — координаты кусочков сладости. Все координаты — действительные числа.

English: M lines follow, containing 2 numbers each — these are coordinates of the cockroaches at the present moment. (M + 2)nd line of the input stream contains the number ??? N (0 ≤ N ≤ 10000) ??? . N following lines contain coordinates of sweet pieces.

Can be the number of sweet pieces equal 0 ? So what will be the answer in this case ?
Answer can be empty ?

Edited by author 07.09.2017 17:23

Edited by author 07.09.2017 17:23

Can somebody tell me why i get memory limit exceeded in test case #9... ????
i make an k-d tree and use nearest neighbor search in my solution and still have memory limit

Edited by author 03.05.2013 07:52

i try, but it isn't enough. give a hint, please (test #6)

Edited by author 01.09.2017 07:46

oh yeah,  nearly 1000 submits, i dont remember

The new time limit for the problem id 4 seconds. With old time limit 5 seconds bruteforce solutions could pass all tests.

Ok, I understand Fortune's algorithm for building Voronoi diagrams. But how to implement answering the nearest point queries? Can it be done without explicitly building full-featured Voronoi diagram and then using another sweeping line on it? I guess, the queries can be answered during building the diagram, without actually building the diagram. But how to generate events "a query point meets parabolic front"? Is it even possible in O(log n)?

I have figured out that the 6th test contains numbers with 8 digits after the decimal point. Is it the maximum alowed or are there tests with more than 8 digits after decimal point. What tollerance shouled be used to compare distances between points? It it neccessary to do it with no error or is there an accepted tollerane?

I have generated several test cases with only 6 digits after decimal point, and doubles doesn't allow to resolve this tests correctly. If there are 8 digits after decimal point and 4 before, it is necessary to store about 24 digits.

1) is is necessary to compare distances between points with no error?
2) What is maximum alowed number of digits after decimal point in input?

test cases:
2
999.969732 999.984915
1414.181493 0
1
0 0
>>>>>
(999.969732 * 999.969732 + 999.984915 * 999.984915 == 1414.181493 * 1414.181493 == 1999909.295143709049)

2
999.856428 999.897768
1414.039753 0
1
0 0
>>>>>
(999.856428 * 999.856428 + 999.897768 * 999.897768 == 1999508.423064301008 < (1414.039753 * 1414.039753 == 1999508.423064301009))

2
999.725264 999.971561
1413.999196 0
1
0 0
>>>>>
(999.725264 * 999.725264 + 999.971561 * 999.971561 == 1999393.726288646417 > (1413.999196 * 1413.999196 == 1999393.726288646416))

Edited by author 31.05.2016 18:21

Edited by author 20.12.2017 21:41

Time Limit so small. Solution with O(n * m) complexity passed tests with time 3.244s.

http://acm.timus.ru/status.aspx?space=1&num=1369&author=124588

Is this a valid test case?

2
-9999 -1
-9999 1.00000000000000000001
1
9999 0

I know the answer should be 1. But it's hard to code.



Edited by author 08.03.2014 14:22

I wrote kd-tree based solution but still TL#16, and I cannot find bad cases for my realization (on my local machine it finishes within 1 sec on any test). Any ideas of what kind of tests may these be?

Edited by author 26.03.2013 04:00

Edited by author 26.03.2013 14:03

Russian: Далее следуют M строк по 2 целых числа в каждой — координаты тараканов в настоящий момент. M + 2 строка содержит число N (0 ≤ N ≤ 10000). Далее N строк — координаты кусочков сладости. Все координаты — действительные числа.

English: M lines follow, containing 2 numbers each — these are coordinates of the cockroaches at the present moment. (M + 2)nd line of the input stream contains the number N (0 ≤ N ≤ 10000). N following lines contain coordinates of sweet pieces. All coordinates are floating point numbers.

i.e. are integer or float coordinates of the cockroaches ?

Please, decrease Time Limit to 4 second (for example)!

Edited by author 30.07.2011 00:01