Доброе утро!
Насколько мне известно, здесь любят решать всякого рода задачки. Поэтому хотел бы поделиться с вами информацией о конкурсе, который мы запустили около 2х недель назад. Задача классическая и предельно простая: нужно найти ближайшую точку к заданной из набора точек в 3D пространстве (с рядом ограничений и допущений на точность).
Автор решения, которое пройдет по рамкам точности и будет работать быстрее всех, получит от нас символический приз размером в 5 000 рублей. Конкурс продолжается до 15 октября 2013 года, участвовать могут жители России, достигшие 18 лет. Остальные могут участвовать вне конкурса.
Зарегистрироваться и ознакомиться с правилами можно на странице конкурса.
Текст задачи
Ограничение времени: 20 с
Ограничение памяти: 64 M
Дана карта глубины — прямоугольное изображение размера n x m пикселей. Значения пикселей p(i,j), 1<=i<=n, 1<=j<=m, — целые неотрицательные числа. Ненулевые пиксели представляют собой связную область: от любого пикселя этой области можно построить путь до любого другого пикселя этой области, переходя только к соседним пикселям, также лежащим в этой области. Соседними пикселями будем называть пиксели, имеющие общую сторону. Описанное изображение является перспективной проекцией некоторого множества трехмерных точек D. Формула преобразования точек на изображении в точки трехмерного пространства приведена ниже.
x = p(i,j) * (j — (m + 1)/2 ) / 576
y = p(i,j) * ( (n + 1)/2 — i) / 576
z = p(i,j)
Требуется выполнить k запросов на поиск «близкой» точки из вышеописанного множества к некоторой заданной точке трехмерного пространства a_i, i=1,...,k. «Близкими» к точке a_i будем называть точки множества D, расстояние от которых до точки a_i не более чем на 50 превышает расстояние от точки a_i до множества D. Расстоянием от точки до множества называется минимальное расстояние от этой точки до точек этого множества.
Формат входных данных
В первой строке содержится два целых числа — n и m (1<=n<=240, 1<=m<=320). В каждой из следующих n строк содержатся m целых чисел в диапазоне [0; 65535] — значения пикселей изображения. Далее следует целое число k (1<=k<=100000) — число запросов. В следующих k строках содержатся запросы. Каждый запрос задается координатами точки трехмерного пространства — тремя вещественными числами в диапазоне [-10^4; 10^4]. В каждой строке числа разделены пробелами.
Формат результата
Для каждого запроса требуется на отдельной строке вывести два целых числа через пробел — координаты пикселя в исходном изображении, соответствующего найденной «близкой» точке множества D. Если «близких» точек несколько, то можно вывести любую из них.
Автор: liq
