infoarena

Aici puteţi discuta despre problema Poligon (http://infoarena.ro/problema/poligon).

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

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?

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.

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?  :-s )

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.

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 ....

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.

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.

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.

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

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)

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.

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

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

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

..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

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.

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.

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.

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:
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:
unde f(dreapta, x, y) calculeaza semiplanul in care e situat punctul (x, y) fata de dreapta.

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

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.

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.

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?

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.

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. :annoyed:

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).

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

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)

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

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

:-k


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

o sa il mai downloadez eu..

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

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

raspuns gresit pe testele 6, 9 si 10  :-'

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

 :D
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.

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

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



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

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

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 :D
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  :banana:

Pe testul asta:
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.

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