miraina's blog

By miraina, 13 years ago, In Russian

Как наиболее эффективно и быстро решить эту задачу:

Однажды Дима вышел на улицу погулять. Первым делом он отправился на футбольное поле, но никого там не обнаружил. Его внимание привлекли странные ямки. Как раз этим утром он читал про круги на полях и сразу заподозрил неладное. Более того, он понял, что искать! Он считает, что на поле есть такие четыре ямки, которые являются вершинами квадрата, стороны которого параллельны сторонам поля. Помогите Диме понять, прав ли он.

Входные данные
В первую строку входного файла записано целое число N — количество ямок на поле (1 ≤ N ≤ 2012). Следующие N строк содержат декартовы координаты ямок — пары целых чисел, не превосходящих 1000000 по абсолютной величине. В каждой строке координаты записаны через пробел. Футбольное поле имеет прямоугольную форму. Оси координат параллельны сторонам поля.

Выходные данные
Если Дима прав, выведите в выходной файл через пробел в любом порядке номера ямок, образующих искомый квадрат. Ямки нумеруются с единицы в том порядке, в котором они перечислены во входном файле. Если таких квадратов несколько, выберите любой.
Если квадрата нет, выведите строку NO SOLUTION.

Заранее спасибо за помощь!

  • Vote: I like it
  • +3
  • Vote: I do not like it