Úloha
Koľko kilometrov pásky s nápisom polícia by bolo potrebných na ohraničenie/izoláciu karanténnej oblasti všetkých miest na Slovensku kde sa vyskytlo aspoň 8 potvrdených prípadov?
Údaje o testovaných osobách sú dostupné na stránke Národného centra zdravotníckych informácií, mapu Slovenska z OpenStreetMap môžete stiahnuť z geofabrik.de (podstatné sú body 1001-1003, t.j. veľkomestá,mestá a dediny viď formát dát GIS-OSM)
Takisto môžeme využiť už vytvorenú mapu mapa.covid.chat
Pomocou DevTools
si môžeme zo stránky vybrať vektorový obrázok v SVG formáte. Ten v jazyku Python
spracujeme knižnicou xmltodict
import xmltodict
with open('covid.svg') as fd:
data = xmltodict.parse(fd.read())
print("Počet kružníc: {}".format(len(data['svg']['circle'])))
print(data['svg']['circle'][0])
print(data['svg']['circle'][4])
Počet kružníc: 201 OrderedDict([('@cx', '59'), ('@cy', '340'), ('@stroke-width', '5.897911347683685'), ('@r', '9.610530170360718'), ('@stroke-location', 'inside'), ('@class', 'recovered')]) OrderedDict([('@cx', '167'), ('@cy', '491'), ('@stroke-width', '2'), ('@r', '6.661574496518876'), ('@stroke-location', 'inside'), ('@class', 'infected')])
Spracovanie bodov znázorňujúcich potvrdené prípady:
body = []
for circle in data['svg']['circle']:
if circle['@class'] == 'infected': #zaujimaju nas len potvrdene pripady
body.append((int(circle['@cx']), int(circle['@cy']), float(circle['@r'])))
if len(body) < 6: print(circle['@cx'], circle['@cy'], circle['@r'])
len(body)
374 517 6.661574496518876 167 491 6.661574496518876 202 501 4.902686155817854 337 503 5.897911347683685 349 483 4.902686155817854
196
Filtrovanie podľa polomeru:
vrcholy = [(b[0], b[1]) for b in body if b[2]>=8]
print(len(vrcholy))
print(vrcholy)
13 [(82, 423), (168, 361), (213, 300), (313, 290), (453, 262), (835, 266), (357, 250), (250, 217), (833, 187), (325, 157), (538, 166), (380, 125), (839, 106)]
Policajné pásky - Policajné pásky stále obopínajú … https://bratislava.zoznam.sk/
Sweeping line
¶[0,3,5,7,10,11]
ako zásobník s výberom $k$ prvkov ... $\Theta(n)$Spočítanie konvexnosti 3 za sebou nasledujúcich bodov $A, B, C$:
$$ \tan \alpha \gtreqless \tan{\beta} \hskip{3 cm} \frac{B.y-A.y}{B.x-A.x} \gtreqless \frac{C.y-B.y}{C.x-B.x} $$Aby sa nemuselo riešiť delenie nulou ani práca s racionálnymi/reálnymi číslami, tak sa obe strany vynásobia ...
Po spojení hornej a dolnej časti môžeme spočítať celkovú dĺžku konvexného obalu:
obal = [0,3,5,7,12]
obal_body = [sorted(vrcholy)[i] for i in obal]
print(obal_body)
print(*zip(obal_body, obal_body[1:])) #dvojice susedných bodov
[(82, 423), (250, 217), (325, 157), (380, 125), (839, 106)] ((82, 423), (250, 217)) ((250, 217), (325, 157)) ((325, 157), (380, 125)) ((380, 125), (839, 106))
bodA, bodB = (82, 423), (250, 217)
import math
math.sqrt( (bodA[0]-bodB[0])**2 + (bodA[1]-bodB[1])**2)
265.81948762270986
# https://docs.python.org/3/library/math.html#math.hypot
math.hypot(bodA[0]-bodB[0], bodA[1]-bodB[1])
265.81948762270986
math.hypot(*[a-b for a,b in zip(bodA,bodB)])
265.81948762270986
def dist(p1, p2):
return math.hypot(*[a-b for a,b in zip(p1,p2)]) #funguje aj pre viacrozmerne pre Python3.8+
dist( bodA, bodB )
265.81948762270986
import numpy as np
def dist_np(p1, p2): #vypocitanie euklidovskej vzdialenosti
return np.linalg.norm(np.array(p1)-np.array(p2))
dist_np( bodA, bodB )
265.81948762270986
#Dlzka hornej casti konvexneho obalu
sum(dist(p1,p2) for p1,p2 in zip(obal_body, obal_body[1:]))
884.8911821395161
Máte daných $n$ bodov v rovine. Nájdite najmenšiu vzdialenosť medzi 2 bodmi. Triviálne riešenie v $\Theta(n^2)$:
body = vrcholy
print(body)
[(82, 423), (168, 361), (213, 300), (313, 290), (453, 262), (835, 266), (357, 250), (250, 217), (833, 187), (325, 157), (538, 166), (380, 125), (839, 106)]
vzd = 10**10 #velka hodnota
for b1 in body:
for b2 in body:
if b1 != b2:
vzd = min(vzd, dist(b1, b2))
print(vzd)
59.464274989274024
vzd = dist(body[0], body[1])
n = len(body)
for i in range(n-1):
for j in range(i+1, n): # i < j
vzd = min(vzd, dist(body[i], body[j]))
print(vzd)
59.464274989274024
min([dist(body[i], body[j]) for i in range(n) for j in range(n) if i < j])
59.464274989274024
min(dist(body[i], body[j]) for i in range(n-1) for j in range(i+1,n))
59.464274989274024
Predstavme si, že sme už spracovali niekoľko bodov a vieme, že doteraz najkratšia vzdialenosť je $h$. Pozrime sa na ďalší bod ... ktoré dvojice treba skontrolovať?
Pamätáme si teda len body v sivom páse (teda $[x-h, x]$) a prehľadávame len body podľa $y$-ovej hodnoty $[y-h, y+h]$ ... efektívne pomocou binárneho samovyvažovacieho stromu (hranice nájdeme v $O(\log n)$, počet bodov je $O(1)$).
Jazyk | Štruktúra údajov | funkcie |
---|---|---|
C++ | set |
lower_bound , upper_bound |
Java | TreeSet |
floor , ceiling |
Python | sortedcontainers.SortedSet |
irange , bisect |
https://en.cppreference.com/w/cpp/algorithm/lower_bound
https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html#floor-E-
https://grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedcontainers.SortedList.irange
Milan dostal do daru od starých rodičov rozsiahlu záhradu. Ako moderný gazda-poľnohospodár sa rozhodol, že si kúpi malotraktor. Opantaný reklamou nemenovaného obchodu na nákup "za desatinku, už iba dnes" sa vybral hneď na nákup. V predajni mu ukazovali rôzne malotraktory, nech si kúpi čo najväčší, kde je najviac rôzneho príslušentsva (a stojí samozrejme čo najviac). Zrazu si uvedomil, že v záhrade je niekoľko ovocných stromov, ktoré mu nedovoľujú poorať celú záhradu veľkým traktorom.
Pomôžte Milanovi podľa rozmiestnenia stromov v záhrade určiť maximálnu šírku malotraktora tak, aby ním prešiel medzi ľubovoľné dva susedné stromy.