There are many 2D rectangles in 2D space. Given a point, suppose this point did not hit (inside of) any rectangle, find the one rectangle it is closest to. Assume the rectangles are not rotated. Can it be faster than O(n)?

# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 159 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | PikMike | 152 |

8 | Ashishgup | 151 |

8 | Petr | 151 |

10 | 300iq | 150 |

There are many 2D rectangles in 2D space. Given a point, suppose this point did not hit (inside of) any rectangle, find the one rectangle it is closest to. Assume the rectangles are not rotated. Can it be faster than O(n)?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/15/2018 16:47:30 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I will kinda gloss over technical details for now, feel free to ask for clarifications.

I suppose that you want to answer queries of type "What is the closest rectangle to this point?" in less than

O(n) time. Now shortest distance from the pointPto the rectangle is the shortest distance from thePto one of its sides. The shortest distance fromPto the segmentABis eithermin(|PA|, |PB|) or length of perpendicular fromPtowardsAB, if it lands on the segmentABof course.Now, let's see which case actually happens for rectangle, which is the closest to the point

P. Dealing with second case is simple: we just need to cast 4 rays in all coordinate directions from the pointP, for each ray find the first rectangle they intersect and remin answer with this rectangles (note that because all rectangles are axis-parrallel, all perpendiculars to the sides are axis-parallel too). To deal with the first case, you need to find the closest point toPamong the corners of rectangles: in general, such a problem can be solved with Voronoi diagram (and I am pretty sure that there is not anything significantly simplier in general case), in your case there may be some simpler solution, but I can't see it for now.Total time: precalculation (for Voronoi diagram), per query. It seems that you need something like a persistent treap to answer queries online, but offline you can do a scanline with set to handle both described cases (after you built the Voronoi diagram, of course)).