1 Тема от KinoMan

  • KinoMan
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-16
  • Сообщений: 2

Тема: SGU 394. Berhatton

http://acm.sgu.ru/problem.php?contest=0&problem=394

Кратко о задаче
Во входных данных задаются координаты пиццерий и их зоны охвата. Пиццерии располагаются на плоскости в виде перевернутых на 45 градусов квадратов. Задается число K. Если наша пиццерия находится в зоне действия K или более других пиццерий, то мы ее закрываем. Вывести порядковые номера закрытых пиццерий.

На разборах Southern Subregion 2008 предлагался следующий алгоритм решения.
1. Перевернуть систему координат на 45 градусов и увеличить на корень из 2 все значения координат и длин. (в таком случае они остаются целые).
2. Добавить в массив событий следующие события: квадрат начался, закончился, проверить координату пиццерии. Отсортировать события по координате Х.
3. Пройти по массиву событий (метод сканирующей прямой) и при этом началу квадрата y1 делать операцию "+1", концу y2 "-1" в неком массиве Y. Чтобы узнать количество пиццерий покрывающих данную предлагалось суммировать значения массива от 0 до y0. (y0- координата пиццерии)


В задаче 0<y<10^9. При перевороте системы он еще увеличится.
Просто тупо создать такой большой массив не пройдет по памяти. Пробовал за место массива пользоваться map stl в c++. Все мои реализации не проходили дальше 11 теста.
Прошу помощи и подсказок по решению этой задачи.

2 Ответ от ArtemKadeev

  • Откуда: Ulyanovsk STU
  • Зарегистрирован: 2009-06-12
  • Сообщений: 13

Re: SGU 394. Berhatton

Для решения этой задачи надо как минимум хорошо владеть деревом отрезков. http://e-maxx.ru/algo/segment_tree
Еще там надо провести сжатие координат (т.е. отсортировать их и заменить на порядковые номера в отсортированном массиве)
В этом случае мы сможем задать массив необходимого размера, но по времени тривиальный алгоритм все еще не укладывается, для этого и нужно дерево отрезков.

Также мне кажется, что проще ничего не поворачивать, а дерево строить просто по диагоналям.
Т.е. вместо x и y брать номера диагоналей. Они легко получаются как (x+y) и (x-y+n) - часто использую эту методику для упрощения работы с диагоналями. Т.е. значения функции (x+y) будут равны для точек, находящихся на одной диагонали, которая направлена от верхнего левого угла координат. другая соответственно описывает другую диагональ. Т.о. мы можем хранить в дереве тупо координаты относительно какой либо диагонали, а время событий считать по номерам другой диагонали. Ко второй функции мы должны только прибавить какое-то n, чтобы номера всегда были положительны.

3 Ответ от KinoMan

  • KinoMan
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-16
  • Сообщений: 2

Re: SGU 394. Berhatton

ArtemKadeev
Спасибо большое!
Сдал задачу!