Disconnect the x points. This takes the time "O (n log (n))".
Divide the range into stripes of width 10. (Here you will need obvious information about the pathological case when one point has x-coordinate 1 and the next has x-coordinate 10 20. ) O(n)
For each strip:
- Take the set of dots inside this strip or within x of 5 on each side and sort them by y. This is
O(n log(n)) for all bands. - For each point in the strip, find the Manhattan distance at all other points in a slightly wider strip, whose y coordinate is within 5 of their own. If you find at a distance of 5, go out and report a lie. This is
O(n) for all bands.
Report an error.
This algorithm is O(n log(n)) . I highly recommend that you demonstrate for yourself that the Manhattan pointwise comparison in 1.2 accepts O(n) operations, even if the answer is incorrect.
For truth, this is simple - it follows from the fact that there is a maximum number of other points that can be compressed in a 20x10 box without 2 falling within 5. For false it is more difficult, you can have many other points in this field, but the moment you compared them to the others, you should have found two at a distance of 5. In any case, this point participates in a fixed maximum number of comparisons between points before you answer.