BitCell

Locuitorii orasului DANGER au aflat ca centrala nucleara de pe langa oras are defectiuni. Ei doresc sa stranga bani si sa isi protejeze orasul. Primarul cunoaste exact unde este situata fiecare cladire de pe harta (coordonatele x si y ) si doreste sa angajeze un programator care sa ii rezolve problema :
Primarul vrea un zid rotund (de lungime minima) care sa inconjoare toate cladirile. Doar trebuie sa ii spuneti primarului centrul cercului (zidului rotund) si raza lui. Pentru asta veti deveni eroii orasului.

TEST I (0 puncte)
IN (bitcell15.in)

OUT (bitcell15.out)



TEST II (0 puncte)
IN (bitcell15.in)

OUT(bitcell15.out)


RESTRICTII SI PRECIZARI

• Vor exista cel mult 100000 (o suta de mii) de cladiri ce trebuie inconjurate.
• Vor exista cel putin doua cladiri ce trebuie inconjurate.
• Timp executie (5 sec/test)
• Memorie 25 MB
• Cladirile se considera punctiforme (zidul poate trece prin coordonatele unei cladiri)
• Raspunsul se considera corect daca diferenta in modul dintre raspunsul oficial si cel furnizat de program este mai mica de 0.00001

Data start: 18/9/2011
Finalizare concurs: 24/9/2011
Desemnare castigator: 25/9/2011

Mai sunt cateva zile si se termina concursul si inca nu exista solutii...

Ideea e ca se dau N puncte in plan si trebuie gasit un cerc a.i. sa le contina pe toate. Mai mult, cercul trebuie sa aiba aria minima.

Eu unul din prima zi cand ai postat am inceput sa caut Algoritmi pentru a rezolva asa ceva , i-am citit pe toti si recitit si tot nu am inteles nimic , cam trist ....
Inca mai e timp dar viitorul pare cam sumbru , KBOOM!

Se poate pune de-o prelungire ? Am găsit un algoritm, este vorba de secțiunea 4 din articolul "LINEAR-TIME ALGORITHMS FOR LINEAR PROGRAMMING IN R3 AND RELATED PROBLEMS" de Nimro Megiddo, dar nu am apucat să-l parcurg/înțeleg. Algoritmul este de complexitate O(n), așa după cum demonstrează autorul.

Data start: 18/9/2011
Finalizare concurs: 1/10/2011
Desemnare castigator: 2/10/2011

Spor

Cred ca ar merge si algoritmul asta. Cam greu pentru mine sa il pun in functiune.. ,Daca s-ar prelungi concursul,cred ca as incerca si eu ceva,dar dat fiind timpul cam scurt...

p.s : acuma vazui ca s-a prelungit..go,go..

^Depinde la care te referi. Daca e vorba de cel cu O(n2) nu se incadreaza in timpul alocat pentru o suta de mii de puncte. Bineinteles, testele vor departaja corect solutiile voastre. (Un O(n2) ia 40% din punctaj, un O(n log n) ia 60% din punctaj, iar un O(n) ia 100%)

Eu din prima zi in care s-a postat concursul am tot citit si recitit toti algoritmii de pe internet despre rezolvarea problemei si ori nu i-am inteles (Pe cei scrisi de Megiddo sau Welzl care ruleaza in O(n)) ori aproape i-am inteles dar nu prea am reusit sa implementez.
In fiecare zi am stat cateva ore incercand sa inteleg fara izbanda.

Sincer asteptam cu nerabdare sa mi se curme chinul astazi si sa urmeze alt concurs mai ales ca am vazut ca au fost si concursuri fara castigator.

Asa ca cei care intelegeti algoritmii poate puteti sa ii faceti si pe intelesul noobilor ca mine , scriind vreun articol ceva gen "Smallest enclosing circle problem for Super Noobs" .

Se pare ca inca nu avem nicio solutie. Incerc sa va dau cateva idei de rezolvare:
Trebuie alese cateva puncte care sa apartina unui cerc. In primul rand trebuie sa te descotorosesti de punctele care nu iti trebuie. Deci trebuie alese punctele care fac parte din Infasuratoarea convexa. (acestea sunt cele mai "la margine")
In final se aleg cateva puncte din cele de pe infasuratoare si se incearca determinarea unui cerc care sa cuprinda si celelalte puncte.
Recunosc, implementarea pentru asa ceva dauneaza grav sanatatii
Initial ma gandisem sa dau puncte in spatiu (ceva de genu A(x,y,z)) si sa se calculeze sfera de volum minim care le cuprinde pe toate dar cred ca ma injura mai multa lume pe-aici.

---

L.E. (-- 02 Oct 2011, 10:00 --)

Concursul s-a incheiat. Se pare ca nu avem niciun castigator . Cine propune noul concurs?

Mihai dacă e prin preajmă , iar dacă nu, cine se oferă voluntar. Nu fi trist, ai propus o problemă faină!

Pot sa propun tot eu problema? Va fi mai usoara, promit!

Sure, go for it !