Предположим, вам дано N различных точек с положительной координатой x и положительной координатой y.Для каждой координаты вы должны сформировать прямоугольный треугольник с двумя сторонами, которые соединяют координату и ось X на 45 градусов относительно оси X.Таким образом, прямой угол формируется на пересечении обеих сторон, а гипотенуза треугольника находится на оси х.После того, как вы создали эти треугольники, найдите количество точек из заданных N точек, в которых ни один из созданных треугольников не пересекается с этими точками.
Например, скажем, N = 3, и нам даны точки:(4, 6), (7, 2), (2, 5)
Дополнительные вершины для треугольника точки (4,6): (-2,6), (10,6)
Дополнительные вершины для треугольника точки (7,2): (5,2), (9,2)
Дополнительные вершины для треугольника точки (2,5): (-3,5), (7,5)
В этом примере треугольник, образованный координатой (4,6), будет перекрываться с координатой (7,2), таким образом, правильный результат будет равен 2, поскольку только точки (4, 6) и (2,5) не перекрываются ни с какими созданными треугольниками.
До сих пор я наблюдал, что для проверки, пересекается ли треугольник одной точки с одной из N точек,Вы берете разницу значений y и проверяете, больше ли она равна разнице абсолютных значений значений x или равна ей, так как наклоны сторон треугольникавсегда будет 1. Используя это свойство, мое решение использует квадратичный алгоритм, который сравнивает каждую точку с любой другой точкой в наборе.Однако я хочу решить эту проблему за линейное или линейное время, поэтому мне нужна помощь в написании более эффективного алгоритма.
Примечание: размер значений x и y очень велик, поэтому я не могу использовать решение, котороеимеет итерации, основанные на размерах координат.