Всем привет!
Сразу перейду к задаче — дано множество из N (1 < N < = 105) различных точек с целочисленными координатами на координатной плоскости. Для каждой точки надо найти номер ближайшей к ней точки (из множества, кроме неё самой). Если таких несколько нужно вывести точку с минимальным номером. - 104 < = xi, yi < = 104
UPD Расстояние между точками (x1, y1) и (x2, y2) равно |x1 - x2| + |y1 - y2|. :P
Input
4
0 0
1 1
1 0
0 1
Output
3 3 1 1
Similar problem: Given N points (1<=N<=100000) Draw a straight line that connects maximum number of those points and output the count of those points that are in the straight line.
How is that similar to Azret's problem?
This has no known solution: http://stackoverflow.com/a/2786316
2d — дерево
Можно подробней?
http://algs4.cs.princeton.edu/92search/
Были курсы на coursera.org. Там на видео все объяснялось подробней.
К сожалению у меня в школе стоит фильтр на многие сайты (да, я живу в школе). :P Можно прямо здесь?
К сожалению, курсы то закрываются, то открываются (обычно летом), так что прямую ссылку дать не могу. Но на ютубе или на том же топкодере всегда можно найти что-то про 2d деревья.
А вы про какие 2D деревья говорите? 2D деревья отрезков? :P
Про частный случай kd-дерева
По сути — это бинарное дерево поиска на 2-х измерениях.
Similar problem:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=324&page=show_problem&problem=2392
Incorrect
Это вроде для нахождения самой отдалённой точки насколько я понимаю.
Упс, да.
Rotate the plane by 45 degrees.
Now distance between two points is max(|x1 - x2|, |y1 - y2|).
Points at the same distance represents a square with edges parallel to the axis.
You can use binary search to answer for each point. While checking whether there is a point in the square or not, one can use 2D data structure. Choose a data structure that you are familiar with. I would implement a range tree(with fractional cascading) or a persistent segment tree.
Overall complexity is O(N(logN)2)
I can't understand how the 45 degree rotation works, can anyone explain please?
Your algorithm works in O(N (log n) ^ 2 * log (answer)).
Actually, it is O(NlogNlog(answer)) so O(N(logN)2) is not that bad upper bound too.
You probably missed "fractional cascading" part.
Кто хочет быстро получить ответ на геометрическую задачу? Указывайте ограничения координат и то, что расстояние манхэттенское, после пятой редакции
А есть ссылочка на задачу?
It can be easily solved with 2d segment tree + binary search for answer. For each point lets make binary search for answer. We have to check is there some another point that distance between them is less than answer. How to check it? Lets rotate all points at 45 degree. And for checking current value of binary search we have to calculate some sum at rectangle (Easily with 2d-segment tree).
But, I also think that this problem can be solved with standart divide and conquer method. Just solve it as for Euclidian geometry with another function that calculates distance between two points with abs formula.
First method works in O(n log^3 n). This solution is 100% right :). It is pretty easy to prove that binary search works here.
Second method works in O(n log n), but I have no idea how to prove. It will be fantastic if someone give me prove of it or extra test case.
Всем спасибо! Решил! Бессонная ночь не прошла зря. :)
Кому интересно, вот решение и ссылка на задачу.
Thank you all! Accepted! Sleepless night cost it. :)
For who are interested here is solution.