DomJudge - Balóny¶

jazyk Počet Čas Znakov
C++ 5 0,24 - 2,94 s 794 -1.926 B
Python 7 0,74 - 2,85 s 545 - 1.821 B
Java 18 0,59 - 6,29 s 1.141 - 3.142 B

Ú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 vyskytla slintačka a krívačka?

FMDmapa-1024x540.webp

Ú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

image.png

Spracovanie dát z mapy¶

Pomocou DevTools si môžeme zo stránky vybrať vektorový obrázok v SVG formáte. Ten v jazyku Python spracujeme knižnicou xmltodict image-2.png

In [2]:
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:

In [6]:
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
Out[6]:
196

image.png

Filtrovanie podľa polomeru:

In [10]:
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)]

image.png

Policajné pásky - Policajné pásky stále obopínajú … https://bratislava.zoznam.sk/

image.png

Konvexný obal množiny bodov¶

image-7.png

image-3.png

Zametanie, zametacia priamka Sweeping line¶

  • konvexný obal vytvoríme z 2 častí - horná a dolná časť
  • usporiadame body podľa súradníc $\Theta(n.\log n)$
  • priebežne vytvárame aktuálnu hornú časť konvexného obalu ako spracovávame body zľava doprava

Zložitosť - vytvorenia jednej časti konvexného obalu¶

  • v každom bode niekoľko bodov (0 až počet bodov v obale mínus 1) odstránime z konnvexného obalu a pridáme jeden ďalší
  • konvexný obal môžeme reprezentovať [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$:

image.png

$$ \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:

In [22]:
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))
In [23]:
bodA, bodB = (82, 423), (250, 217)
In [24]:
import math
math.sqrt( (bodA[0]-bodB[0])**2 + (bodA[1]-bodB[1])**2)
Out[24]:
265.81948762270986
In [25]:
# https://docs.python.org/3/library/math.html#math.hypot
math.hypot(bodA[0]-bodB[0], bodA[1]-bodB[1])
Out[25]:
265.81948762270986
In [26]:
math.hypot(*[a-b for a,b in zip(bodA,bodB)])
Out[26]:
265.81948762270986
In [27]:
def dist(p1, p2):
    return math.hypot(*[a-b for a,b in zip(p1,p2)]) #funguje aj pre viacrozmerne pre Python3.8+
In [28]:
dist( bodA, bodB )
Out[28]:
265.81948762270986
In [29]:
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 )
Out[29]:
265.81948762270986
In [30]:
#Dlzka hornej casti konvexneho obalu
sum(dist(p1,p2) for p1,p2 in zip(obal_body, obal_body[1:]))
Out[30]:
884.8911821395161

Najbližšie dva body¶

Máte daných $n$ bodov v rovine. Nájdite najmenšiu vzdialenosť medzi 2 bodmi. Triviálne riešenie v $\Theta(n^2)$:

In [19]:
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)]
In [20]:
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
In [36]:
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
In [39]:
min([dist(body[i], body[j]) for i in range(n) for j in range(n) if i < j])
Out[39]:
59.464274989274024
In [40]:
min(dist(body[i], body[j]) for i in range(n-1) for j in range(i+1,n))
Out[40]:
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ť?

image.png

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

https://docs.python.org/3/library/bisect.html

Ďalšie materiály¶

  • Convex Hull
  • Line Sweep (TopCoder)
  • Voronoi diagram
  • United States of Voronoi (youtube)
  • World Capitals Voronoi
  • Voronoi Diagram Intro Part 1 (youtube)
  • palma.strom.sk - Festivalové leto II

DomJudge - úloha Balenie¶

Firma bAliarne SUciastok dostala zákazku na balenie darčekových predmetov z čokolády. Tieto predmety sú vyrábané na objednávky, teda pre každý druh predmetu je vytvorená forma v tvare podľa požiadaviek. Následne treba zabaliť 10 rovnakých kusov položených na seba do potravinárskej fólie. Na obaľovanie fóliou už má stroj, ktorý sa otáča okolo pracovného stola a fóliu zabalí ľubovoľný predmet (niečo podobné ako sa balia kufre na letisku). Keďže ide o potravinu, tak navyše kvôli trvanlivosti musia nahradiť vzduch technickým plynom. Na určenie výslednej ceny teda potrebujú vedieť koľko plynu treba pre jednotlivé formy naplniť do výsledného obalu.

Vašou úlohou je spočítať, koľko percent z výsledného obaleného balenia tvorí technický plyn (teda jeho podiel na celkovom objeme). Každá forma je zadaná ako 2D obrys, teda súradnice vrcholov na jej obvode. Na obrázku je modrou farbou zobrazená forma, červenou farbou obal z fólie a žltou farbou technický plyn v obale.

image.png