029 Infasuratoare convexa

[•johsonsbabi]

ai facuto tu? dami sursa ta de 100 te rog. eu am facut modificarea aia inainte sa imi spui si nu a mers ,am testato de enspe mii de ori si tot nu ia ultimu test.
ataseaza sursa te rog

[•alexandru92]

Ti-am trimis-o printr-un pm

[•S7012MY]

la indicatii de rezolvare ar trebui adaugat si qhull.
Ma poate ajuta cineva sa-mi modific sursa astfel incat sa afisez punctele in ordine trigonometrica si sa nu mai iau kbs?
infoarena.ro/job_detail/475962?action=view-source

[•ilie.danila]

Eu cred ca in momentul in care faci testele ar trebui sa verifici ceea ce zici la "date de iesire". Eu am scris punctele corect si cu toate astea iau 20 de puncte pentru ca nu am sortat punctele pe axa x ci pe y. La date de iesire nu vad nicaieri sa se ceara ca  punctle din fisieru de iesire sa inceapa de la punctul cu cel mai mic x. La mine de exemplu incep de la cel cu cel mai mic y. Si ma astept sa iau punctaju. Ceea ce nu se intampla. Eu cred ca cel mai bine ar fi sa adaugati acest detaliu "mic" la date de iesire sau sa depuneti putin efort sa verificati corectitudinea fisierului de iesire, nu daca respecta un template...

[•vladii]

Ai omis un mic detaliu:
"Pe urmatoarele H linii se vor gasi cele H puncte ce alcatuiesc poligonul, in ordine trigonometrica.".

[•ilie.danila]

Le-am scris in ordine trigonometrica, am verificat cu fisierele de teste. Doar ca am inceput cu punctul cu y-ul cel mai mic.
Apropo, tu din chestia aia cu ordinea trigonometrica ai inteles ca ele trebuie orientate pe axa x? )

[•vladii]

M-am uitat pe teste si se incepe mereu cu punctul cel mai din stinga - jos. Intr-adevar in enuntul problemei nu se incepe cu acel punct si poate induce lumea in eroare . Dar oricum, din modul de functionare al algoritmului (Graham), cind introduci prima data exact acel punct in stiva (si care evident nu va mai fi scos niciodata), se poate da seama care va fi primul punct care trebuie afisat.

LE: Scuze, acum (si inainte, nu stiu sigur, nu m-am uitat) exista un evaluator si cred ca se poate incepe cu orice punct

Si cred ca pentru intreaga arhiva educationala si pentru intreaga infoarena s-a depus destul efort, btw.

[•wefgef]

Uitandu-ma peste evaluator, am descoperit un bug care nu avea legatura cu problema enuntata de tine. Care este id-ul jobului despre care sustii ca ar trebui sa primeasca 100?

[•ilie.danila]

Vezi tu, Andrei, intre job #481942 (0 puncte) si job #481846 (100 puncte) singura diferenta e axa pe care am ordonat punctele (deci si odrinea in care au fost puse pe stiva si ulterior afisate) dar sunt exact aceleas puncte si respecta ordinea trigonometrica (cum se cere in enunt). De aici inteleg ca fisierele de iesire sunt verificate linie cu linie, nu este neaparat verificata corectitudinea lor.

E ca si cum ai afisa informatia dintr-o lista circulara de doua ori incepand de la doua noduri diferite si uitandu-te la rezultat ai trage concluzia ca nu e vorba de aceeasi lista in cele doua cazuri.

[•wefgef]

Se pare ca nu reparasem bugul bine. Fixed!

Revenind la comentariul tau initial: care este sursa in care afisezi punctele bine si nu primesti 100?

[•ilie.danila]

Era vb de job #481942 care lua 0 puncte, acu m-am uitat si a luat 100.

[•wefgef]

Cum sa fie vorba despre job #481942? L-ai trimis la mult timp dupa primul tau post.

Hai sa incercam sa rememoram sirul intamplarilor:

Programul tau initial lua 20 de puncte nu pentru ca sortai dupa y, ci pentru ca nu foloseai setprecision(). Ai modificat la inceput sortarea (primeai tot 20 de puncte), iar apoi ai folosit si setprecision() si ai luat 100 de puncte. Candva in intervalul asta ai postat pe forum, folosind un ton intelept, apostrofandu-ne pentru munca jalnica pe care am depus-o si dandu-ne sfaturi despre cum sa iti evaluam sursa. Dupa ce ai postat, eu am luat sursele si testele, am rulat programele local si am vazut care e problema. Am descarcat evaluatorul (DA, chiar aveam un evaluator de la inceput care NU verifica respectarea unui template) si am descoperit un bug obscur care nu afecta in niciun fel punctajele primite de tine. Am modificat greseala (prost), am reevaluat si am postat pe forum. In continuare, tu ai trimis doua surse, una care sorteaza dupa x, si alta dupa y, ambele folosind setprecision(). Din cauza fix-ului meu prost, sursa care sorta dupa y lua 0 (cu evaluatorul initial ai fi luat 100). Dupa penultimul tau post, am remodificat evalul (de aceasta data bine) si am reevaluat. Sursele tale dinaintea primului post tot 20 primesc si acum.

Concluzii:

• La inceput vorbeai tampenii.
• E foarte smechera functia setprecision().
• E bine sa ai useri aroganti pe forum, mai gasesti buguri cu ocazia asta.

[•Marius]

Cum sa fie vorba despre job #481942? L-ai trimis la mult timp dupa primul tau post.

Hai sa incercam sa rememoram sirul intamplarilor: ...

Concluzii:

• La inceput vorbeai tampenii.
• E foarte smechera functia setprecision().
• E bine sa ai useri aroganti pe forum, mai gasesti buguri cu ocazia asta.

Genial. )

[•dornescuvlad]

Salut! Imi poate explica si mie cineva pe un desen atasat eventual cum sa-mi aleg punctul urmator in functie de unghiul polar format (m-am documentat, am gasit tot felul de chestii cum ar fi (cross product, sa verific daca punctul p[ i ] e deasupra liniei formate de ultimele doua consecutive)..m-am chinuit de 3 ore sa inteleg dar nu prea reusesc..Am vazut tot felul de functii care calculeaza un semn..nici alea nu le-am inteles.Am incercat si cu arctg() si arccos() la inceput dar aveam doua cazuri si n-am reusit sa le deslusesc.  :oops:m
Va rog sa nu ma luati prea tare!!!

[•tinky]

@vlad eugen: punctul urmator il alegi in functie de sensul lui trigonometric in raport cu ultimele 2 puncte din infasuratoare. Si sensul trigonometric se calculeaza cu determinanti (cred ca asta nu ai inteles tu din functiile respective).
Sensul a 3 puncte (a,b,c) este calculat prin urmatorul determinant:
|a.x a.y 1|
|b.x b.y 1| = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y)
|c.x c.y 1|
Daca e mai mare decat 0 punctele sunt intr un sens si daca e mai mic decat 0 sunt in celalalt sens (nici eu nu stiu exact care sens e care dar cu o foaie in mana afli repede); daca determinantul e 0 atunci punctele sunt coliniare.

Tip pentru viitor: abs(determinantul de mai sus) reprezinta dublul ariei acelui triunghi.

Acum am si eu o intrebare: stie cineva cum functioneaza setprecision. Momentan am cos 100 de puncte cu setprecision(20) dar nu stiu exact ce inseamna 20-ul ala

[•GaborGabriel]

Salutare, am o intrebare.
De ce programul dupa ce calculeaza panta prin : (float)(A[p2].y-A[p1].y)/(float)(A[p2].x-A[p1].x); imi afiseaza 1.#INF ca fiind panta 2-5 ( pe testul oficial ) ? Ce semnifica #INF ?
Multumesc

Later Edit: scuze pentru dublu post
pentru a fi mai clar : am structura

Cod:

struct punct {
	int x,y;
	float p;
}A[100];

dupa ce stabilesc extrema stanga si o pun pe pozitia 1, fac urmatorul for

Cod:

for(i=2;i<=n;i++)
		A[i].p=calculeaza_panta(1,i);
double calculeaza_panta(int p1,int p2)
{	
	return (float)(A[p2].y-A[p1].y)/(float)(A[p2].x-A[p1].x);
}

Later Edit : Raspuns : pentru ca punctul 2 si punctul 5 au acelasi x ( 0 ) si deci panta e infinit.

Editat de moderator: Nu mai posta de mai multe ori consecutiv pe acelasi subiect. Editeaza posturile anterioare.

[•dspMihai]

Am incercat si eu problema dar nu iese. Dupa ce am sortat dupa unghiurile polare m-am cam blocat. Poate cineva care a obtinut 100p sa se uite prin sursa mea sa imi indice vreo greseala?
Si stiti daca au ceva special sursele 6,7,8?
Va multumesc.

[•S7012MY]

Nu merg problemele de pe tju (

[•pauldb]

Problema Wall se gaseste si aici.

[•nash]

Nu este obligatoriu sa faci cautarea unui punct de pe invelitoatea convexa si sa sortezi in jurul lui. Poti sa faci sortarea si relativ la un punct aleator ( ex.: ( 0 , 0 )  ) . Doar ca la sfarsitul scanarii mai trebuie facute niste verificari.

[•nash]

De ce daca aplic sort() peste un vector de elemente de genul ( la care am implementat operatorul "<") :

Cod:

class vect {
public:
    float x,y;
    
    vect():x(0.0f),y(0.0f) {}
    
    vect(int X,int Y):x(X),y(Y) {}
    
    const int operator<(const vect& aux)  const{
        if(x * aux.y - y * aux.x  > 0.0f) return 1;
        if(x * aux.y - y * aux.x <=0.0f) return 0;
    }
    
    vect operator-(const vect& aux) const {
        return vect( x - aux.y , y - aux.x );
    }
};

mi le sorteaza descrescator ?
Conform specificatiei daca "<" este corecta trebuie sa intorc true (1). pentru: "a<b" vectorul din stanga este mai mic fata de cel din dreapta daca produsul lor vectorial este mai mare ca 0 ( adica am intoarcere la stanga in cercul trigonometric ).
In cazul asta de ce mi le sorteaza descrescator?(dupa unghi) Adica... e suficient sa schimb semnele si o sa fie crescator... dar de ce face asa?

[•SpiderMan]

Dupa mine, linia cu return 1 din comparare returneaza 1 daca x > y. Adica uite :

Cod:

x * aux.y - y * aux.x  > 0.0f <-> x * aux.y > y * aux.x

Daca ai sorta un vector normal, de int cu o functie care face cam ce faci tu mai sus, adica :

Cod:

bool comp (const int &a, const int &b) {
    return a > b; // sau if (a > b) return 1; else return 0;
}

Teoretic le sorteaza descrescator, ceea ce face si functia ta. Incearca sa schimbi 1 cu 0 si ar trebui sa mearga  .

[•nash]

Pe minue nu ma intereseaza sa schimb un semn... ca asta am vazut si eu( dupa cum am mai scris ) pe mine ma intereseaza sa imi dau seama unde este eroarea logica....

in ceea ce priveste linia respectiva... logic e corect:
operator< face: A X B > 0  => unghi(B) > unghi(A) => unghi(A) < unghi(B)  ( intoarcere la stanga... sens trigonometric ) si atunci este true ...

Scuze... gresala mea... rezultatul era bun... nu interpretam eu bine rezultatul...

[•Xladhenian]

Ma poate ajuta cineva cu sursa http://infoarena.ro/job_detail/770389 ?

Evaluatorul zice poligon gresit, dar daca rulez testele local obtin rezultatul corect (diff -w zice ca fisierele sunt identice, grader_eval scrie mesajul "corect10").

Edit: Mi-am dat seama care era problema, s-a rezolvat.

[•SebiSebi]

Daca pot fi puncte coliniare pe infasuratoare ce trebuie modificat la scanarea Graham?
Multumesc!