Как наиболее эффективно и быстро решить эту задачу:
Однажды Дима вышел на улицу погулять. Первым делом он отправился на футбольное поле, но никого там не обнаружил. Его внимание привлекли странные ямки. Как раз этим утром он читал про круги на полях и сразу заподозрил неладное. Более того, он понял, что искать! Он считает, что на поле есть такие четыре ямки, которые являются вершинами квадрата, стороны которого параллельны сторонам поля. Помогите Диме понять, прав ли он.
Входные данные
В первую строку входного файла записано целое число N — количество ямок на поле (1 ≤ N ≤ 2012). Следующие N строк содержат декартовы координаты ямок — пары целых чисел, не превосходящих 1000000 по абсолютной величине. В каждой строке координаты записаны через пробел. Футбольное поле имеет прямоугольную форму. Оси координат параллельны сторонам поля.
Выходные данные
Если Дима прав, выведите в выходной файл через пробел в любом порядке номера ямок, образующих искомый квадрат. Ямки нумеруются с единицы в том порядке, в котором они перечислены во входном файле. Если таких квадратов несколько, выберите любой.
Если квадрата нет, выведите строку NO SOLUTION.
Заранее спасибо за помощь!
Не проверено, но должно работать. Решение работает.Группируем точки по x (или y, в зависимости от того, где менее населенные группы получаются) - O(n)
Цикл по всем группам
В пределах группы x рассматриваем все пары (x,y1) и (x,y2), d=y2-y1 и проверяем есть ли точки (x+d,y1) и (x+d,y2).
если мало точек с одинаковыми x или y, то получается O(n)
если много точек с одинаковыми x и одновременно много с одинаковыми y, то O(n*n)
можно немного пооптимизировать. например можно пропустить рассмотрение наиболее населенной группы и т.п.