Намерете кръстосана линия през 3 точки по хоризонтални линии - алгоритъм, структури от данни, геометрия

Като се има предвид група от n точки, които се разпространяват на 3 хоризонтални линии (y = 0, y = 1, y = 2) помислете за алгоритъм, за да откриете дали има пресичаща линия с O (n ^ 2)

въведете описанието на изображението тук

Отговори:

Вярвам, че този алгоритъм в O (n ^ 2). Първо предполагаме:

1. Най- x- координира точките на линията y=2 може да бъде представен от ограничен брой битове.
2. Че тези x-координати са първоначално сортирани в x, Ако не, тогава сортирането им първо е O (nlog (n))
3. Дефиницията на пресечната линия се прави по отношение на точността на представяне на точките с крайния брой битове.

Сега конструирайте функция хеш, както следва:

1. Намерете минималното разстояние между съседни точки на линията y=2, Тъй като xКоординатите се сортират, това е O (n). Обадете се на това минимално разстояние d.
2. Хеш функцията е пода (2 * х / г). Ясно е, че този хеш ще начертае всяка точка y=2 до уникален контейнер. Тази операция е също O (n).

След това направете следното:

1. За всяка двойка точки по линиите y=0 и y=1, изчислява се пресича y=2, Това е О (n ^ 2).
2. За всяка точка на пресичане y=2, търсенето на таблицата хеш, за да видите дали има точка от линията y=2 там. Ако има, вижте дали то е същата точка (с точност на машината) и ако е така, тогава има пресечна линия. В противен случай, няма. Това е O (n ^ 2), тъй като търсенето на хеш е O (1).

Следователно алгоритъмът е О (n ^ 2). Няма код, просто идеи.