Rešitev zelo dodatne naloge

Zelo dodatna naloga (za dolgočasene)

Kako dolga bi bila vrv, ki bi jo napeli okrog teh krajev? Upoštevaj, da se vrv ne dotika vseh krajev, temveč le tistih, ki so "izpostavljeni", tistih v sredi, recimo Ljubljane, pa ne.

Rešitev

Saj vemo: tole je zelo dodatna naloga, drži?

Če v Google vtipkate computational geometry, bo prvi zadetek, kot vedno, kazal na Wikipedijino stran o Computational geometry. Na strani je spisek znanih problemov iz računske geometrije in prvi med njimi je konveksna ovojnica, Convex hull. Za domačo nalogo ste morali odkriti kak algoritem za iskanje konveksne ovojnice. Problem je bil najbrž pretežak, vendar je bilo tudi razmišljanje o njem čisto koristna telovadba.

Sam sem si zamislil algoritem, podoben algoritmu Graham scan. Vem, da je koordinatno izhodišče znotraj poligona, ki ga iščem. Vse točke uredim glede na kot, ki ga oklepajo z izhodiščem. Za računanje tega kota uporabim funkcijo atan2. To je tak, malo inteligentnejši arcus tangens. Zelo uporabna reč, spomnite se nanjo, ko boste računali kote.

from math import *
kraji = sorted(kraji, key=lambda ixy: atan2(ixy[2], ixy[1]))

Če bi povlekel črto med tako urejenimi točkami, bi dobil

Čeprav izgleda neuporabno, je že precej blizu. Zdaj se zapeljem čez vse trojke točk in preverim ali gredo posamična trojka v smeri urinega kazalca. Če je tako, pobrišem srednjo točko izmed njih. To ponavljam, dokler ne morem pobrisati ničesar več.

Celoten program je takšen

from math import *
kraji = sorted(kraji, key=lambda ixy: atan2(ixy[2], ixy[1]))

while True:
    i = -1
    prej = len(kraji)
    while i < len(kraji) - 1:
        _, ax, ay = kraji[i - 1]
        _, bx, by = kraji[i]
        _, cx, cy = kraji[i + 1]
        if (bx - ax) * (cy - ay) - (cx - ax) * (by - ay) < 0:
            del kraji[i]
        else:
            i += 1
    if len(kraji) == prej:
        break

Tole nikakor ni najhitrejši možni algoritem. Je pa najpreprostejši in - razen rokohitrskega urejanja na začetku in brisanja elementa (del kraji[i]) - sploh ne presega tega, kar smo se doslej učili pri predmetu. V smislu programiranja, se razume. V smislu razmišljanja, ki je za algoritmom, pa je to seveda upravičeno "zelo dodatna naloga".