Pagini recente » Diferente pentru preoni-2005/runda-3/solutii intre reviziile 19 si 20 | Istoria paginii blog/cautare-binara | Diferente pentru preoni-2008/runda-1/5-8 intre reviziile 19 si 20 | Diferente pentru runda/acs_pc_2017-2018_winter_break_12314132 intre reviziile 4 si 5 | Diferente pentru fmi-no-stress-2012/solutii/cercuri4 intre reviziile 2 si 3
Nu exista diferente intre titluri.
Diferente intre continut:
h1(#cercuri4). 'Cercuri4':problema/cercuri4
h1(#cercuri4). 'Cercuri4':problema/cercuri
Solutie O(N ^ 2 + NlogN)
Se sorteaza cercurile descrescator dupa raza, deoarece un cerc cu o raza R nu poate fi inclus decat intr-un cerc cu o raza R1 >= R.Dupa sortare toate cercurile ce pot include cercul i se vor gasi inaintea acestuia. Astfel putem aplica un algoritm asemanator celui de cel mai lung subsir crescator pentru a obtine frumusetea maxima, relatia de recurenta obtinuta fiind Fmax[ i ] = Frumusete[ i ] + max(Frumusete[ j ] | j < i si cercul j include cercul i).
Pentru a verifica incluziunea a 2 cercuri (C1,R1) respectiv (C2, R2) urmatoarea relatie trebuie satisfacuta : distanta(C1,C2) + min(R1,R2) <= max(R1,R2). unde C reprezinta centrul cercului iar R raza .
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
