062 Poligon

[•domino]

Aici puteţi discuta despre problema Poligon.

[•Matrix]

am luat o eroare urata de compilare la problema asta,
" /usr/lib/gcc-lib/i486-linux/3.3.5/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:98: undefined reference to `main'
collect2: ld returned 1 exit status

"
va rog sa imi spuneti ce inseamna ?? ??

multumesc anticipat

[•stifmeister]

Am folosit faptul ca un punct este interior unui poligon numai daca dreapta paralela cu Ox care il contine intersecteaza intr-un numar impar de ori laturile poligonului la dreapta punctului.
Am luat numai 60 de puncte pentru ca am depasit timpul de executie.
Exista o alta metoda de rezolvare, mult mai eficienta? Sau trebuie sa-mi imbunatatesc algoritmul?

Si o intrebare pentru organizatori: dupa cat timp este oprit un executabil dupa ce a depasit timpul de executie? Daca in "Monitorul de evaluare" am la un test timp de executie "0.31s" pentru o problema care admite numai 0.2 sec, inseamna ca programul meu s-a oprit dupa 0.31 sec sau ca evaluatorul la oprit fortat?

[•Cosmin]

Ai luat cam mult 60 de puncte ... cu rezolvarea ta trebuia sa iei 50, oricum eu am testat limitele numai in pascal ... daca testam si in C faceam altfel testele, cat despre solutie ai primit si mail si articolul cu solutiile e pe prima pagina a siteului info.devnet.ro da parca ai mai avut problema asta si pt rezolvarile din runda 2. La articol ii zice preONI 2005 runda #3 - solutii. Am vazut ca intrebi la multe probleme ... se vede ca ONI bate la usa.

[•domino]

Am folosit faptul ca un punct este interior unui poligon numai daca dreapta paralela cu Ox care il contine intersecteaza intr-un numar impar de ori laturile poligonului la dreapta punctului.
Am luat numai 60 de puncte pentru ca am depasit timpul de executie.
Exista o alta metoda de rezolvare, mult mai eficienta? Sau trebuie sa-mi imbunatatesc algoritmul?

Si o intrebare pentru organizatori: dupa cat timp este oprit un executabil dupa ce a depasit timpul de executie? Daca in "Monitorul de evaluare" am la un test timp de executie "0.31s" pentru o problema care admite numai 0.2 sec, inseamna ca programul meu s-a oprit dupa 0.31 sec sau ca evaluatorul la oprit fortat?

Eu zic sa citesti mai atent ce scrie pe site inainte sa pui intrebari.. exista articol cu solutii cat si in monitor s-a explicat ce e cu timpul de executie (ca nu este 100% exact)... daca programul tau s-a incadrat in limita de timp,atunci iti va afisa timpul cat a rulat, iar daca scrie "Time Limit Excedeed" scrie timpul cand l-a oprit evaluatoru (logic, nu?   )

[•Sergiu]

Coord sunt alese in asa fel incat produsul a oricaror coordonate sa se incadreze in longint?  adica x1*y2<=maxlongint?

PS: Trebuiau facute teste mai smecheroase ca pe FP cu metoda lui stifmeister se pot lua 80 pct.

[•Cosmin]

Tu din faptul ca coordonatele sunt <=60000 ce deduci??? De implementat am implementat doua metode, brute force si metoda jmechera, considera ca daca iei 100 pe asta esti bazat ....

[•Sergiu]

Pai  60000^2=3.6 miliarde>maxlongint si daca am doua puncte (unul al poligonului si celalalt punctul de verificat), prin metoda mea (determinant) imi moare.  Da la nici un test n-am primit wrong answer, deci ori nu sunt, ori  apar perechi de cate 2 si nu-mi influenteaza verificarea.  100 pct nu-mi va fi greu sa iau din moment ce ati publicat solutiile (interesante,  n-am ce zice). Trebe doar sa fac ceva modificari.

[•Cosmin]

Adevarul e ca din cate tin eu minte numerele sunt mai mici de 30000, pt ca asa am generat testele, nu am vrut sa fie si dificultatea asta in problema dar solutia oficiala nu ar fi avut probleme cu depasirea longintului pentru ca am lucrat cu numere reale nu intregi. Oricum spor la implementare.

[andreit1]

WA peste WA. Desi la toate testele facute de mana( vreo 20 la numar)imi iese corect( adica acelasi rezultat ca si un BF facut in timpul concursului). Daca are cineva niste teste mai 'smenoase' care imi dea si mie WA mi-ar fi de mare ajutor.

[andreit1]

Ar putea sa imi explice si mie ce inseamna 'Too bad!' si care sunt cauzele pentru care programul meu nu ajunge la sfarsitul executiei???

[•unholyfrozen]

o mica intrebare referitoare la solutia publicata in articol pt 100 p
spune acolo ca noi pt fiecare din punctele poligonului formam acele benzi etc
dar daca unul din cele m puncte are o abscisa pe care nu se afla nici un punct al poligonului ?
eu am luat toate coordonatele x ale celor m puncte, dar cum era de asteptat 2 teste mi-au dat TLE si unul "Too bad!" (aici chiar nu shtiu de ce)

[•Cosmin]

Nu inteleg intrebarea ... explica mai bine, eventual da un exemplu. S-ar putea sa nu fi inteles tu explicatia solutiei si sa te gandesti la cu totul altceva.

[•unholyfrozen]

da..eu consideram o "banda" = dreapta  
am inteles acum, si sper sa o fac klumea
multumesc oricum

[•unholyfrozen]

ok.. am reimplementat putin ...
Testul 6 imi da "too bad"
am testat cateva situatii particulare precum segmentele verticale,punctele de pe marginea dreapta a unei benzi, punctele de pe segmente, punctele care au abscisa mai mica/mare decat cea minima/maxima etc
daca avetzi alte situatii sau daca se poate da testul 6 v-as fi recunoscator

[•bogdan2412]

Am si eu o intrebare: cum faci a doua cautare binara dupa ce ai gasit banda in care se afla punctul m? Exista cazuri in care un punct e deasupra mijlocului unei drepte, dar totusi este sub dreapta din cauza orientarii acesteia. Ex: http://www.bogdan2412.lx.ro/poligon.htm

[cristi8]

http://www.bogdan2412.lx.ro/pol.png

..vezi ca lx.ro nu te lasa sa dai linkuri la imagini direct.. mie imi da "You are not authorized to view this page" cand incerc sa intru pe linkul tau.
Fa un .html in care pui imaginea

[•Cosmin]

Pai cand ai dreptele din banda curenta sortate dupa punctul ce e pe dreapta si la mijlocul benzii, mai tii si un indice inspre dreapta respectiva, sau coeficientii dreptei ca sa poti vedea daca punctul e deasupra dreptei ,sub dreapta sau pe dreapta, ai avut nevoie de punctul de mijloc doar pentru ordinea relativa a dreptelor.

[•bogdan2412]

Nu mai, stiu sa vad daca un punct este deasupra unei drepte sau sub ea.
Ideea e ca nu inteleg cum cauti binar deasupra cator drepte e punctul curent.
Uita-te pe linkul de mai sus, ca l-am modificat. Daca caut binar dupa mijloace ar iesi ca e deasupra a 3 drepte, pentru ca toate mijloacele au inaltimea mai joasa decat cea a punctului curent. Dar de fapt e doar deasupra a 2 drepte.
Zi-mi si mie mai detaliat cum faci cautarea binara, te rog.

[andreit1]

Dupa cum zicea si Cosmin mai sus, mijloacele sunt folosite doar pentru a obtine o ordine a dreptelor. Cautarea binara o faci tinand cond doar de faptul ca punctul este desupra sau dedesubtul unei drepte. Fiind sortate dupa mijlocul acelui segmentul, pentru primele drepte( cele de sus) punctul va fi dedesubt, iar pentru restul deasupra... tu trebuie sa cauti 2 segmente consecutive astfel incat punctul este desupra unuia si dedesubtul celuilalt.

[•Cosmin]

Sa verifici de care parte e un punct fata de o dreapta poti face folosind semnul expresiei a * x_curent + b * y_curent + c, unde a, b si c sunt coeficientii dreptei, daca expresia are rezultatul 0 atunci punctul e pe dreapta iar daca expresia e pozitiva punctul e intr-un semiplan iar daca e negativa e in semiplanul opus. Daca vrei sa testezi fata de un segment si nu fata de intreaga dreapta poti folosi determinantul:

Cod:

 | x  y  1|
 | x1 y1 1|
 | x2 y2 1|

care are un semn daca cele trei puncte sunt ordonate trigonometric si semnul opus daca sunt ordonate in sens orar ... nu mai stiu care semn pentru care ordine si cand fac un program de obicei potrivesc pe loc semnul, pentru chestii de baza de geometrie te poti uita in cormen, in cartea lui Mihai Stroe si in urmatoarele linkuri: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1 , http://www.faqs.org/faqs/graphics/algorithms-faq/

In problema asta limita de timp e destul de stransa deci prima metoda cu coeficientii merge mai repede daca pentru fiecare dreapta ii calculezi o data si dupaia ii folosesti.

La mine cautarea binara e ceva de genu:

Cod:

while (hi-lo>1) do begin
       midl:=(hi+lo) shr 1;
       if f(dreapta[midl],xp,yp)<0 then hi:=midl
       else if f(dreapta[midl],xp,yp)>0 then lo:=midl
       else begin
           hi:=midl;
           lo:=midl;
       end;
end;

unde f(dreapta, x, y) calculeaza semiplanul in care e situat punctul (x, y) fata de dreapta.

[•bogdan2412]

Ok. Multumesc mult. Am inteles acum... Limita de timp e foarte stransa si iau doar 70, dar poate o sa reusesc sa o scot la capat pana la urma

[•unholyfrozen]

Totusi  ce trebuie sa optimizez sa iau 100 ?..Testul 6 imi iese idin timp. Cautare binara facuta klumea, sursa clara, bine implementata si tot iau 90 . Mi se pare limita de timp putzin cam mica totusi.

[•Cosmin]

Timpii au fost setati dupa sursa mea in pascal, care nu cred ca am optimizat-o constient, pur si simplu am implementat ideea. Limita de timp s-ar putea totusi sa fie prea stransa, daca folosesti C++ ar fi bine sa folosesti metoda sort() din STL ca merge mult mai repede decat metoda qsort. Probabil diferenta intre C++ si Pascal e la citire si ai putea optimiza citirea, din nou pentru fiecare dreapta poti calcula o singura data coeficientii a b si c si sa verifici pe ce parte e x, y fata de dreapta facand ax + by + c, nu sa recalculezi de fiecare data numerele a, b si c. Sper ca sfaturile iti vor fi folositoare.

[•unholyfrozen]

din pacate nu folosesc C++ ci doar C si eu nu calculez dreapta ca ecuatie de genul ax+by+c=0 ci determin daca este deasupra sau dedesubtul ei cu produsul incrucisat (evit lucrul cu numere reale) . Asta ar trebui sa imi reduca timpul de executie nu?