infoarena

Aici puteţi discuta despre problema Rubarba (http://infoarena.ro/problema/rubarba).

In articolul cu solutiile pentru runda #2 cls XI-XII era mentionata o tehnica de programare numita "Rotating Calipers" (http://cgm.cs.mcgill.ca/~orm/rotcal.html ).
Articolul este deosebit de interesant dar nu am avut nici o idee buna ca sa pot sa-l implementez. A incercat cineva sa foloseasca aceasta tehnica pentru problema "Rubarba" sau pentru alte probleme care accepta o astfel de rezolvare? Am mare nevoie de ajutor. ( de fapt, nu stiu cum sa compar 2 unghiuri determinate fiecare de cate 2 drepte).

La Rotating Calipers din cate tin eu minte nu ai nevoie decat de produs scalar a doi vectori si eventual de functia distanta, unghiul dintre doua drepte nu apare nicaieri ... De asemenea daca nu stii chestii de baza in geometrie poti sa te uiti peste linkurile de aici http://info.devnet.ro/forum/viewtopic.php?t=236 . Mai bine sa stii bazele si sa iti iasa in O(h^2) problema si dupaia sa te bagi la chestii de finete.

La problema asta iau 70 pct, pt. k pe 3 teste primesc WA. Cum am facut eu: dupa ce am construit infasuratoarea convexa, am luat fiecare segment de pe infasuratoare ca dreapta suport d pt. una din laturile dreptunghiului. Aflam din punctele ramase ale poligonului care este cel mai departat de dreapta d ( prin acest punct duceam || la d, care era directia celui de-al doilea segment al dreptunghiului ). Apoi aflam si punctele M si N din cele ramase din care, daca ducem perpendiculara pe directia aleasa, intersecteaza dreapta suport cel mai sus ( respectiv cel mai jos ), si aflam si ultimele doua directii. Cel mai de sus punct de pe dreapta suport initiala era considerat a fi cel care are ordonata (y) cea mai mare, si pentru y egali, x-ul cel mai mare.
  As vrea sa stiu daca rationamentul este corect.  
  Daca este corect, pot aparea erori de la precizie? Am lucrat pe double.

                             Filip b.

same problem. Numai ca iau 50 de p. La afisare tre sa rotunjim rezultatul sau trebuie afisat nerotunjit? (am trimis o sursa cu rezultat rotunjit si am luat 50 p, apoi am trimis cu rezultat nerotunjit si am luat 30 p).

S-a gandit cineva ca poate ati gresit la infasuratoarea convexa? (pot exista si puncte coliniare)

Incercati testul asta:
8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0

raspuns: 4

Din pacate imi da si mie 4... Spun din pacate pt. k daca nu imi dadea asa, descoperam unde e greseala...  :cry:

Salut!
Iau 80 - 90pcte pe problema asta si chiar nu inteleg ce gresesc. Am modificat afisarea, am pus long double in loc de double, am incercat tot ce se poate incerca si tot nu reusesc sa iau 100pcte.  :'(
Am vazut ca sunt destui baieti care luau 80 (incorect pe testul 7 si 9) si care apoi au luat 100. Vreau sa stiu si eu ce ati modificat.
Multumesc!

LE: Am luat 100 punind rezultatul pe double si tratind separat cazul cind pantele sunt infinite. M-am chinuit ceva, oricum, frumoasa problema :)

Desenul de la explicatie nu este corect.
Dreptunghiul cu aria 50.32 e asta:

(http://a.imageshack.us/img824/379/19787136.png)

asa e cum zice Ionut,desenul lor nu e corect :thumbdown:

wow , such wrong answer, how get not wrong answer?

Salutare

Poate cineva care are acces la teste sa imi zica si mie testul 2 ? Nu reusesc sa iau suta si chiar nu ma prind de ce...  ](*,)

Daca si cei care au 100 si-ar putea da seama ce gresesc, as aprecia foarte mult.

http://www.infoarena.ro/job_detail/1235441 (http://www.infoarena.ro/job_detail/1235441)

Multumesc