АиСД лабораторная работа
Задача:
Даны прямоугольники на плоскости с углами в целочисленных координатах ([1..109],[1..109]). Требуется как можно быстрее выдавать ответ на вопрос «Скольким прямоугольникам принадлежит точка (x,y)?» И подготовка данных должна занимать мало времени. UPD: только нижние границы включены => (x1<= x) && (x<x2) && (y1<=y) && (y<y2)
В файле first_way реальзован алгоритм перебора
В файле second_way реальзован алгоритм на карте
В файле third_way реальзован алгоритм персистентного дерева отрезков