nagyon szep vizualizacio lett, kosz :P
3d-ben voronoi diagram az sajnos lassu es nagyon nem trivialis,
megprobaltam egy elore megirt (voro++) programmal megoldani, de egy
picit is nagyobb peldara 24 giga ramot kezdett el hasznalni, es orakig
ment, ami nem jo na
kulonben irtam ra backtrackes oct-tree-t, es rendes inputra kevesebb
mint 1 sec alatt lefut, szoval nem kell branch-and-bound
Engedy, Balazs <engedy.balazs(a)gmail.com> írta (2011. március 19. 1:18):
Sziasztok!
Én pedig a maximális minimum távolságos "Safest Place" feladattal
foglalkoztam egy kicsit. Csináltam hozzá C#-ban egy kis szemléltető
programocskát [1], ami persze tesztelni is jó, hogy miként alakul a rács.
Hogy jól vizualizálható legyen, ez csak 2D-ben működik, így oct-tree helyett
quad-tree-t használ, de a működése alapelvét tekintve ugyanaz, mint a 3D
verziónak.
Közben amúgy rájöttem, hogy egy jó megoldás kapható úgy is, ha építünk a
pontokra egy Voronoi-diagramot ([2]), ennek ugyanis valamelyik csúcspontja
lesz a megoldás. Persze nem valószínű, hogy valakinek ezt lenne ideje
lekódolni...
[1]:
http://cs.bme.hu/acm/felkeszito2011/05/SafestPlaceVisu.zip
[2]:
http://en.wikipedia.org/wiki/Voronoi_diagram
Üdv,
Balázs
On Fri, 18 Mar 2011 23:01:07 +0100, NGG <ngg(a)ngg.hu> wrote:
megcsinaltam alien gamet, de nem tudtam
bekuldeni, mert szar a
bekuldorendszeruk es amig szamol visszafele hogy 6 perc van hatra,
kozbe irja hogy time expired azzal parhuzamosan...
nagyon szep megoldasa van kulonben
6 perc van megoldani, bekuldessel egyutt, szoval olyan megoldas kell,
ami kb 5 perc alatt lefut
enyem O(n^2*log(n)), es kb 5 mp alatt lefut a nagy inputfajlra, amiben
kb 45 bazinagy eset van
nem szeretnem elarulni megoldast (majd jovohet penteken), csak
sejtesekrol par szo:
- tenyleg nem szamit hogy ki mit lep, mindenkepp ugyanaz nyer (sot a
lepesszam is azonos mindig)
- a masik sejtes nem igaz, hogy 1-et irhatunk akarmilyen pozitiv szam
helyett (pl "0 -1 1 0"-ra 1 lepes utan van vege, amig "0 -1 2 0"-ra
2
lepes utan van vege)
ngg
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato