Текущ брой на Списание ИнфоМан
 


Турнир за Купата на Декана - 2005, Задача A

Уловието на задачата може да прочетете тук.

Решение

В задачата се търси правата, която минава през най-много от дадените точки. По дадени две точки (X1, Y1), (X2, Y2) уравнението на правата минаваща през тях е решение на системата:

A * X1 + B * Y1 + C = 0

A * X2 + B * Y2 + C = 0

ако X1 == X2 се получава:

A = 1; B = 0; C = -X1

Този случай се разглежда, за да се избегне ситуацията, когато съществуват двойни точки. Защото при X1 == X2 и Y1 == Y2 ако се разглежда общия случай се получава A=0, B=0 и C = 0, което не отговаря на нито една реална права.

ако X1 != X2 се получава:

A * (X1 – X2) + B * (Y1 – Y2) = 0

от където:

A = Y1 – Y2

B = X2 – X1

C = - A * X1 – B * Y1 = - (Y1 – Y2) * X1 – (X2 – X1) * Y1 = - Y1 * X1 + Y2 * X1 – X2 * Y1 +X1*Y1= Y2 * X1 – X2 * Y1

Възможни са няколко решения на задачата с различна сложност.

1.       O(N3)

По всяка двойка точки се построява права по указания по-горе начин. За всяка точка се проверява дали лежи върху правата (AX + BY + C = 0). Във всеки един момент се пази текущата най-добра права и броят на точките, които лежат на нея. При срещане на по добра права се обновява най-доброто решение до момента. Броят на правите е N2, за всяка права се проверяват N точки => сложността на решението е O(N3).

2.       О(N2logN)

По всяка двойка точки се построява правата с уравнение Y = m*X + k или X = c, в зависимост от точките. При X1 = X2 уравнението е X = X1, a при X1 != X2 се получава системата:

Y1 = m * X1 + k

Y2 = m * X2 + k

от където

m = (Y1 – Y2) / (X1 – X2)

k = Y1 – m * X1

следва да се обърне внимание на факта, че при целочислени координати m и k са рационални числа.

Създава се масив с всички прави от вида: Y = m*X + k и масив със всички прави от вида: X = c (за всяка права се пази двойката (m, k) или c). Максималната дължина на някой от тези масиви е N2. След сортиране на масивите, преброяваме колко точки принадлежат на всяка права чрез линейно обхождане на масивите. Ако всички двойки точки участват при построяването на масивите, то борят на точките лежащи на дадена права е равен на броя на срещанията на правата в някой от масивите. Сортирането отнема O(N2logN2) = O(N2logN). Построяването на масивите и намирането на резултата отнемат време O(N2), от където следва че сложността на решението е O(N2logN).

3.       O(N2)

Решението е същото като т. 2, но вместо да се строи масив с всички прави, правите се добавят в хеш таблица, която съдържа ключ – уравнението на правата и стойност броят на точките принадлежащи на дадената права. При „хубава” хеш функция, добавянето и търсенето в хеш-таблицата е константна операция. Следователно добавянето на всички прави ще отнеме O(N2) време. След това се намира най-голямата стойност пазена в хеш таблицата и се извежда уравнението на правата.

Автор: Красимир Добрев


обратно към текущ брой