2011/3/19 NGG <ngg@ngg.hu>

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@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@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@sziami.cs.bme.hu
>> http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
>
> _______________________________________________
> acm-valogato mailing list
> acm-valogato@sziami.cs.bme.hu
> http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
>
_______________________________________________
acm-valogato mailing list
acm-valogato@sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato