062 Poligon

[•Cosmin]

Cred ca e diferenta mare intre sortarea in C++ si sortarea in C, iar la produse incrucisate tu ai acolo niste factori care sunt constanti pentru o dreapta si orice alt punct.

[•bogdan2412]

Pe Infoarena imi merg in general mai repede programele in C++. Mi s-a intamplat sa iau TLE cu programul in C si sa iau 100 cu exact acelasi program compilat cu C++. Pe Usaco mi s-a intamplat exact inversul, deci e cam ciudat.

[•unholyfrozen]

Mie in general imi merg sursele mai rapid pe C. Oricum am inteles care e ideea, cand tu calculezi coeficientii o singura data, dar mi se pare mai elegant cum fac eu si nu cred ca ar trebui sa conteze daca aleg intre lucrul cu numere reale si fara (tinand cont ca nu conteaza prea mult precizia).

[•Cosmin]

Eu ma refeream la diferenta intre functia sort din STL si functia qsort din C.

[•spatarel]

Am facut si eu problema asta, si dupa ce am implementat-o prima data, am dat un submit, si am luat 10 .
Asa ca am facut de mana un test, ca sa scap de WA
Acest test ar trebui sa verifice daca trati toate cazurile particulare, dar nu verifica daca lucrati corect pe numere reale!
Asa ca, daca il folositi, aveti grija sa folositi Eps in comparari, unde este cazul
Raspunsul corect este 312.
Sper sa va ajute!

http://www.savefile.com/files/4845550

[edited by svalentin] datele au fost puse intr-un fisier (citeste postul meu de mai jos)

[•Cosmin]

Scurt post ). Puteai totusi sa il pui online undeva si sa zici adresa ...

[•svalentin]

datele au fost puse intr-un fisier pe un site:
http://www.savefile.com/files/4845550

(era prea mare ca sa ramana in stare "bruta" pe forum )
... scuze de intarziere

savefile.com e un site destul de interesant, tocmai bun pentru astfel de situatii, cand vrei sa faci niste fisiere publice (maxim 60MB free space.. chiar si fara inregistrare)
check it out:
http://www.savefile.com/index.php?aff=82981

[cristi8]

When will my file be deleted?
- All files with no downloads for 14 days will be deleted.
Please note that this limit can be lowered to 10 days in extreme cases.

..deci nu e bine ce-ai facut, svalentin

[•svalentin]

When will my file be deleted?
- All files with no downloads for 14 days will be deleted.
Please note that this limit can be lowered to 10 days in extreme cases.

..deci nu e bine ce-ai facut, svalentin

o sa il mai downloadez eu..

[•diana]

imi puteti spune, va rog, cateva cazuri particulare? iau doar 70 de puncte si nu stiu unde gresesc... 

[•Cosmin]

Ce mesaje primesti? Ca depasesti timpul sau ca raspunzi gresit?

[•diana]

raspuns gresit pe testele 6, 9 si 10 

[•Cosmin]

Daca nu explici ce faci, nu am cum sa stiu ce cazuri ai putea gresi.

[•diana]

 
paaai, impart poligonul in mai multe benzi verticale, iar pt fiecare banda tin minte laturile care o intersecteaza (sortate dupa mijloacele segmentelor ce se formeaza). pentru un punct (x, y) caut binar banda in care se afla, iar apoi caut (tot binar, in banda respectiva) sa-l incadrez intre doua segmente consecutive a.i. punctul meu sa fie deasupra primei si dedesubtul celei de-a doua.

[•Cosmin]

Ai incercat sa iti generezi teste aleatoare, si sa compari rezultatele rezolvarii naive cu cele ale rezolvarii mai eficiente?

[•diana]

da... am dat vreo 200 de teste aleatoare si raspunsurile date de cele doua programe sunt echivalente 
Later edit:  am reusit. mi-am descoperit bug-ul la al 269-lea test  acum am luat 100. cosmin, multumesc oricum



[Modificat de bogdan2412: Nu mai postati de 2 ori consecutiv]

[•Cosmin]

felicitari ca ti-a iesit, e destul de dura problema.

[•mathboy]

Rezolv problema ca in solutia oficiala, cautare binara pe benzi, apoi cea de-a doua cautare pe banda respectiva, unde vad deasupra cator laturi se afla punctul dat.
Totusi iau wrong answer pe 5 teste, mi-am testat sursa cu cateva teste mai mici pe care imi da bine si nu realizez ce poate fi gresit. Daca m-ar ajuta cineva, i-as ramane profund recunoscator
LE: Voi cum ati facut cand ati trasat benzile si o latura a poligonului intersecta doar intr-un punct acea banda (adica erau doar tangente in exteriorul benzii) ?
LLE: Se pare ca greseam la intersectia segmentelor cu banda. Am luat 100P in sfarsit 

[•repp4radu]

Pe testul asta:

Cod:

8 1
3 0
5 2
4 4
0 5
-5 4
-5 3
-4 2
-1 0
-1 1

imi da 0 in loc de 1, cu sursa de 100 de puncte. Am incercat si pe alte surse de 100 si nici acelea nu il luau.

[•alexalghisi]

Poate posta cineva un test mai maricel ? Testele mele manuale nu sunt indeajuns pentru descoperirea bugului