029 Infasuratoare convexa

[•pauldb]

Aici puteti discuta despre problema Infasuratoare convexa din Arhiva educationala.

[•APOCALYPTO]

in aceste teste exista si coordonate negative??? teoretic ar trebui. practic mi se pare ca nu pentru ca pe aceiasi sursa doar cum  modificarea output-ului pe infoarena iau 100 iar pe campion 60 restrictiile sunt cam la fel

[•wefgef]

Ai acces liber la teste, poti sa te uiti daca vrei.

[•philip]

In sursa data ca exemplu pentru al doilea algoritm (scanarea Graham) e folosita o functie "semn" care calculeaza daca unghiul format de 3 puncte este mai mare sau mai mic de 180 de grade:

Cod:

long double semn(int i1,int i2,int i3)
{
	return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}

Cum s-a ajuns la aceasta formula?

[•Mishu91]

Acea "formulă" este defapt dublul ariei triunghiului format de cele 3 puncte, însă în cazul de față te interesează doar semnul. Acea arie se calculează cu ajutorul determinanților.

[•philip]

Acea "formulă" este defapt dublul ariei triunghiului format de cele 3 puncte, însă în cazul de față te interesează doar semnul. Acea arie se calculează cu ajutorul determinanților.

Mersi, am inteles. E ca si la calcularea convexitatii unui poligon cu ajutorul determinantilor, luand cate 3 varfuri consecutive.

[•cosgb]

  am o mare problema...am trimis sursa am luat niste timpi ff mari asa ca am luat primele 2 teste si am testat-o acasa in c++ ca sa vad timpul... spre surprinderea mea timpii au fost in jur de 4 ms(raspunsurile de asemenea corecte), dar pe infoarena iau TLE la primul test si SIGCEV la al 2-lea test(restul testelor nu le-am verificat cert e ca pt toate imi iese din timp sau iau SIGCEV, dar primele 2 mie imi merg acasa). Nu inteleg din ce cauza patesc asta(ultima sursa trimisa e cea buna, de fapt e identica cu prima, restul sunt diferite). Ma poate ajuta cineva? (ultima sursa daca se poate uita cineva pe ea) 

[edit]
mi-am dat seama ce e gresit :p am ceva la quicks sort . mai ramane sa corectez aia )

[editat de admin] Nu posta consecutiv, foloseste butonul "modifica"!

[•Bogdan_tmm]

Vroiam sa intreb de ce e nevoie sa luam cel mai de jos (cel mai din stanga) punct daca folosim scanarea Graham... dar in timp ce formulam intrebarea mi-am dat seama ca trebuie ca primul punct din stiva sa fie sigur pe infasuratoare.Daca e asa inseamna ca putem lua si cel mai de sus punct(cel mai din stanga),cel mai de sus (cel mai din dreapta) si toate combinatiile astea(in principiu extremitatiile)... asa e?
LE Am inteles .ms

[•sima_cotizo]

Practic tu rotesti planul, deci poti sa il iei si pe cel mai "de jos" pe o directie care face 43 de grade cu orizontala, iar apoi pe cel mai "din stanga" pe o directie perpendiculara pe prima. Daca faci ajustarile necesare, da, merge.

[•Bogdan_tmm]

Si daca ar fi puncte coliniare, cum realizez sortarea?
Eu folosesc functia

Cod:

inline int cmp(p a,p b)
{
	long double A=(b.x-Min.x)*(a.y-Min.y);
	long double B=(a.x-Min.x)*(b.y-Min.y);
	return A<B||(A==B&&(a.x<b.x||a.x==b.x&&a.y<b.y));
}

dar nu merge.
Daca avem
* *
*     *
* * *
le sorteaza bine pe cele de jos (coliniare) insa cele coliniare de pe verticala sunt luate de jos in sus si ar trebui de sus in jos.
Eu incerc sa formez un poligon.Intrebarea e cum ordonez punctele intr'un sens(trigonometric sau invers)?

[•sima_cotizo]

Ce algoritm folosesti?

In cazul algoritmului care se foloseste de o stiva (parca se numea scanare Graham), nu conteaza foarte mult daca mergi trigonometric sau nu. In acea functie de testare de "intoarcere la stanga/dreapta" (pe care o faci cu produs vectorial) doar schimbi sensul unei inegalitati. Totusi, cred ca nu exista o "regula" pentru ce vrei tu, ar trebui facuta o tratare separata. Poti insa in caz de puncte coliniare pe laturi sa le iei doar pe cele mai departate (capetele practic) in infasuratoare si atunci cand sortezi trigonometric (sau in sens invers) mai folosesti si un test de "distanta" (punctele cele mai departate de punctul de referinta sa fie primele). Sper sa nu ma insel...

[•Bogdan_tmm]

Nu imi trebuia pentru problema asta. Pur si simplu sa sortez in sens trigonometric. Ideea cu distanta pare buna. O sa implementez imediat si revin cu rezultatu:D. Nu am voie sa elimin varfuri din poligon.
LE: faza cu distanta nu merge fiindca pentru punctele de jos coliniare imi trebuie sortate in ordine crescatoare(in functie de distanta) iar cele de pe verticala in ordine descrescatoare:D
Mie imi trebuie pt problema mosia, dar mi s-a parut mai bine sa postez aici.
Deci fiind date n puncte, cum le ordonez in sensul acelor de ceasornic sau invers .Punctele formeaza un poligon convex.

[•sima_cotizo]

LE: faza cu distanta nu merge fiindca pentru punctele de jos coliniare imi trebuie sortate in ordine crescatoare(in functie de distanta) iar cele de pe verticala in ordine descrescatoare:D

Nu cred ca e vorba de "pe verticala" ci "punctele de pe ultima latura a poligonului", fie ea verticala sau nu.

Cat despre sortare in sens trigonometric in jurul unui punct "ref":

Cod:

30.bool comp(point A, point B) {
31.    double dx1 = A.x-ref.x, dx2 = B.x-ref.x;
32.    double dy1 = A.y-ref.y, dy2 = B.y-ref.y;
33.    return dx1*dy2 > dx2*dy1; // varianta: return atan2(dy1,dx1) > atan2(dy2,dx2);
34.}

Functia asta poate fi folosita cu sort() din STL. Codul l-am luat din sursa mea de la problema din arhiva, dar cred ca din orice sursa de 100 poti invata cate ceva

[•Bogdan_tmm]

Pana la urma am luat cel mai de jos stanga punct din poligon,am adunat si la x si la y  0.0010007(ca sa nu mai fie coliniare cu celelalte) si am sortat in jurul acelui punct si a mers de 100
Functia ta e exact ca a mea... Dar nush cum ai luat 100, probabil ca ai luat ref un punct random din cele ale poligonului,dar daca se dadeau puncte astfel incat sa fie coliniare 3 cate 3 nu mai mergea.
Inainte sa incerc ideea de mai sus am facut media aritmetica a tuturor punctelor si mai adaugam la x si la y un 0.0010007(...) dar am observat ca nu sorteaza bine. Mai pe scurt am luat un punct in interiorul poligonului si am sortat varfurile in jurul acelui punct. Ce ar fi gresit? Am folosit aceeasi functie de sortare.

[•sima_cotizo]

Functia ta e exact ca a mea... Dar nush cum ai luat 100, probabil ca ai luat ref un punct random din cele ale poligonului,dar daca se dadeau puncte astfel incat sa fie coliniare 3 cate 3 nu mai mergea.

Nu vor exista puncte coliniare pe infasuratoarea conexa.

Asa am luat 100 la problema din arhiva educationala.

Mai pe scurt am luat un punct in interiorul poligonului si am sortat varfurile in jurul acelui punct. Ce ar fi gresit? Am folosit aceeasi functie de sortare.

Nu poti face asta in Scanarea Graham. Trebuie sa incepi cu un punct care este obligatoriu pe infasuratoarea convexa si poti fii sigur ca cel mai din jos-stanga se afla acolo. La fel si cu sus-dreapta. In principiu primul punct nu poate fi scos din stiva si de aceea nu poti sa il folosesti pe unul din interiorul poligonului (asigura-te ca stapanesti modul de functionare al algoritmului  ).

[•Bogdan_tmm]

Nu ne prea intelegem )
"Mie imi trebuie pt problema mosia" am scris mai sus... Daca poti sa citesti inca o data ce am scris mai sus si ma poti ajuta ti-as ramane recunoscator:D

[•johsonsbabi]

salut.
stie cineva ce trebuie adaugat la scanarea graham pentru a include in infasuratoare si punctele coliniare?

[•alexandru92]

Cod:

semn( ... ) >= 0 // nu > cum e in sursa oficiala

Asta ar fi tot

[•Bogdan_tmm]

>= scoti din stiva daca punctele formeaza o intoarcere la dreapta sau daca sunt coliniare
> scoti din stiva doar daca punctele formeaza o intoarcerela dreapta
Deci lasi cu > insa trebuie modificata sortarea

[•johsonsbabi]

da aveti dreptate, am incercat aia ieri dar este un caz particular. chick this

intra :
8
0 -2
1 -1
2 0
1 1
0 2
-1 1
-2 0
-1 -1

el le sorteaza asa:

1(punct initial) 2 3 4 5 6 8 7

iar cand el ajunge la 8 7 sa le bage in stiva, il baga prima data pe 8 pentru ca asa este in sortare!!!! iar dupa ce il baga pe 7 este aria pozivita si il scoate pe 8 si il baga pe 7



atentie in functie de cum fac sortarea... daca ii bag in functia de comparare a sortarii tg1 > tg2, se sorteaza unghiurile cu tg egala descrescator,  iar daca pun tg1>=tg2 ,unghiurile cu tg egala se sorteaza crescator...
astfel scap de problema de la 6 7 8 dar apare alta la  2 3 4

[•Bogdan_tmm]

Problema asta o tot intrebam si eu pe forum dar nu mi-a raspuns nimeni...
Pana la urma am dat eu de o kestie.
iei primu punct(cel mai de jos stanga,sau oricare dp extremitate) si adaugi la x un 0.00010007 sau orice numar fff mic, iar la y adaugi la fel un numar random 0.00010003 de exemplu.
Si bagi punctu asta in stiva si faci scanarea in mod normal si o sa mearga.
daca poligonul este convex poti sa faci media aritmetica a tuturor punctelor(dupa x si dupa y) si sortezi asa
int cmp(p x,p y)
{
   return atan2(a.y-medie.y,a.x-medie.x)<atan2(b.y-medie.y,b.x-medie.x);
}

[•johsonsbabi]

Problema asta o tot intrebam si eu pe forum dar nu mi-a raspuns nimeni...
Pana la urma am dat eu de o kestie.
iei primu punct(cel mai de jos stanga,sau oricare dp extremitate) si adaugi la x un 0.00010007 sau orice numar fff mic, iar la y adaugi la fel un numar random 0.00010003 de exemplu.
Si bagi punctu asta in stiva si faci scanarea in mod normal si o sa mearga.
daca poligonul este convex poti sa faci media aritmetica a tuturor punctelor(dupa x si dupa y) si sortezi asa
int cmp(p x,p y)
{
   return atan2(a.y-medie.y,a.x-medie.x)<atan2(b.y-medie.y,b.x-medie.x);
}

am citit si posturile tale inainte sa postez eu, dar nu prea am inteles ce ai intrebat . in fine

deci ca sa inteleg:

adun la punctu inditial niste miimi si dupa fac sortarea?


EDIT: da frate ms mult, esti super

[•Bogdan_tmm]

L.E. Vezi ca ti-am lasat un pm

[•johsonsbabi]

baga in`u asta si spunemi cate puncte iti intra in infasuratoare.
(sunt coordonate naturale)

testul este ultimul de la problema cetati de pe campion.

raspunsul corect este 10000 (toate punctele fac parte din infasuratoare)
mie imi ia in infasuratoare 5004. nu stiu de ce

[•alexandru92]

Pentru problema  cetati de pe campion este suficient sa faci modificarea mentionata de mine mai sus