infoarena

Aici puteti discuta despre problema Drepte3 (http://infoarena.ro/problema/drepte3).

Folosind ideea din solutia oficiala am procedat astfel :
-am initializat xmin=xmax=x intersectie d1,d2
-am initializat ymin=ymax=y intersectie d1,d2
-am stabilit daca am dreapte verticale si/sau orizontale si am intersectat cu toate celelalte drepte actualizand solutia. am eliminat aceste drepte din calcul (implicit am modificat n cu 0 1 sau 2 )
- am sortat dupa a[ i ] / b[ i ]. am intersectat dreptele i si i+1 cu i=1..n-1
- am sortat dupa b[ i ] / a[ i ]. am intersectat dreptele i si i+1 cu i=1..n-1
la fiecare intersectie am actualizat solutia

Cu toate astea am obtinut 60 puncte ( WA pe 4 teste ). Poate cineva sa imi sugereze ce gresesc?

folosesc tipul double pentru coeficienti si pentru coordonatele intersectiilor.
citesc pe int si fac conversie (explicita) la double.
folosesc comparare directa pentru double ( x<y ) nu cu un epsilon foarte mic.
Afisez cu printf("%.5lf",...
L.E.
Pot exista doua drepte care sa coincida?

Daca C[1],C[2],..,C[NC] sunt dreptele cu panta pozitiva si D[1],D[2],...,D[ND] dreptele cu panta negativa, ambele siruri fiind sortate crescator dupa panta,si DO dreapta orizontala, DV dreapta verticala (daca exista), atunci singurele puncte care conteaza sunt acelea situate la intersectia dreptelor:
- C[k] cu C[k+1]
- D[k] cu D[k+1]
- C[NC] cu DV
- D[1] cu DV
- C[NC] cu D[1]
- D[ND] cu DO
- C[1] cu DO
- C[1] cu D[ND]
- DV cu DO
Asa ar trebui sa fie acoperite toate cazurile.
Nu cred ca exista drepte identice deoarece o dreapta e paralela cu ea insasi.

Imi poate explica si mie cineva de ce daca initializez xmax xmin yman ymin cu x si y rezultate din intersectia dreptei verticale cu cea orizontala iau 100 si daca initializez cu orice altceva iau 10. Plus ca daca e un test fara o dreapta verticala sau orizontala ar trebui sa dea aiurea.  :eyebrow:
PS Fac cum o explicat mihai_florea mai sus.

Nu vreau sa jignesc pe nimeni, dar nu prea inteleg ce vrea sa zica in solutie.Cea mai mare nedumerire incepe cu propozitia asta:
-Sortăm toate dreptele după ordinea lor pe y dacă ar fi intersectate de o dreaptă verticală cu x-ul foarte mic.
Cum sorteazi dupa ordinea lor pe y?...Poate cineva sa-mi explice in termenii strict matematici?
                                                                                                                                            Multumesc anticipat.

Consideri o dreapta d verticala care trece prin punctul (-infinit, 0). Intersectezi dreptele tale cu d si le sortezi in functie de odonatele punctelor de intersectie.

Am inteles, multumesc...

HELP!!  :'(
cum trebuie afisat rezultatul in pascal???
eu am ceva de genul writeln(x:0:0); si iau 10 pct
daca scriu writeln(x:0:5); iau 0
help pls !!  ](*,)

Ca sa rezolv problema am folosit urmatorul algoritm: iau dreptele, le sortez dupa tangenta, si intersectez apoi fiecare doua consecutive. Am taiat sortarea din program, si ... 100! Dreptele sunt date sortate in fisierul de intrare. Ar fi bine sa modificati testele, sau sa scadeti limita de timp. Job-ul cu sursa mea: http://infoarena.ro/job_detail/352796

in legatura cu articolul de solutii, am o neclaritate

avem dreptele d: ax+by+c=0 si d1: a1x+b1y+c=0
si vrem sa le sortam dupa y la intersectia cu o dreapta de ecuatie x=-infinit

stim ca y=(-a/b)*x -c/b si y1=(-a1/b1)*x - c1/b1 . x fiind foarte mic c/b si c1/b1 devin neglijabile(exact ce scrie in articol) ... deci mie imi ramane sa compar (-a/b)x cu (-a1/b1)x. in articol scrie ca y>y1 daca -a/b>-a1/b1 dar calculele sunt cam asa:

y>y1 => (-a/b)*x > (-a1/b1)*x , x<0 => -a/b < -a1/b1 , contrar a ceea ce scrie in articol. sa'mi zica cineva daca gresesc si unde gresesc.  :-k

Salut!
 Imi poate spune si mie cineva de ce coordnatele colturilor pot fi obtinute numai din intersectia dreptelor consecutive(ordonate crescator dupa panta) ?
Eu nu am mai rezolvat probleme de acest tip si vreau sa prind ideea.

Multumesc anticipat!

O parte a problemei e gasirea intersectiei cu cel mai mic x posibil.  Daca duci o dreapta verticala undeva mai la stanga de prima intersectie, cele n drepte vor fi intersectate in o ordine data de pantele lor. Acum baleind la drepta ordinea in care dreptele intersecteaza dreapta de baleiere ramane aceeasi pana cand intalnim primul punct de intersectie. De aici e clar ca primul punct de intersectie apare intre doua drepte consecutive ca ordine pe dreapta de baleiere.

In cartea Introducere in Algoritmi este descris un algoritm de determinare a intersectiilor pentru un set de n segmente folosind metoda de baleiere. Ideea de aici e o simplificare a unor observatii din algoritmul respectiv.