infoarena

Aici puteti discuta despre problema Infasuratoare convexa (http://infoarena.ro/problema/infasuratoare) din Arhiva educationala (http://infoarena.ro/arhiva-educationala).

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

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

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:


Cum s-a ajuns la aceasta formula?

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.

 ](*,) 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"!

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

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.

Si daca ar fi puncte coliniare, cum realizez sortarea?
Eu folosesc functia
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)?

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

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.

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":

Functia asta poate fi folosita cu sort() din STL. Codul l-am luat din sursa mea (http://infoarena.ro/job_detail/290525?action=view-source) de la problema din arhiva, dar cred ca din orice sursa de 100 (http://infoarena.ro/monitor?task=infasuratoare&score_begin=100) poti invata cate ceva :)

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

Asa am luat 100 la problema din arhiva educationala. :)


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

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

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

Asta ar fi tot :)

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

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

(http://img717.imageshack.us/img717/2339/37917837.png)

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

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

(http://img716.imageshack.us/img716/3327/91643058.png) (http://img716.imageshack.us/i/91643058.png/)
L.E. Vezi ca ti-am lasat un pm

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

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

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

Ti-am trimis-o printr-un pm :)

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

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

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

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

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

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

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?

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.

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?

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

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.

Genial. :))

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!!! :peacefingers:

@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 :-?

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

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

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.

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.

Nu merg problemele de pe tju :((

Problema Wall se gaseste si aici (http://acm.timus.ru/problem.aspx?space=1&num=1185).

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.

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


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?

Dupa mine, linia cu return 1 din comparare returneaza 1 daca x > y. Adica uite :
Daca ai sorta un vector normal, de int cu o functie care face cam ce faci tu mai sus, adica :
Teoretic le sorteaza descrescator, ceea ce face si functia ta. Incearca sa schimbi 1 cu 0 si ar trebui sa mearga  :-k.

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

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.

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

Daca exista puncte, care au acelasi unghi polar relativ cu punctul de start, atunci sunt eliminate toate cu exceptia celui cu coordonata x maxima.

nu se presupune ca putem alege orice punct ca referinta(atata timp cat este pe infasuratoare)? am luat 0 pentru ca imi afisa o permutare CIRCULARA a solutiei corecte :eyebrow:

Esti sigur ca erau in ordine trigonometrica?

Sugerez să nu se folosească doar STL (fără vectori declarați static) pentru această problemă (cum am încercat eu, din plictiseală), implementarea mea obține 50pct, cu TLE-uri :(

O imbunatatire la algoritmul lui Andrew: gasim cele 4 puncte ce reprezinta extremele pe ambele axe (xmin, xmax, ymin, ymax) si eliminam toate punctele din interiorul patrulaterului determinat de acestea. Sortam punctele ramase si de aici algoritmul ramane neschimbat. In acest fel complexitatea devine O(nlog(nr)) unde nr reprezinta numarul de puncte din afara patrulaterului mentionat.
Diferenta de timp nu e extrem de mare, insa mi s-a parut o idee interesanta :). 
Un exemplu de implementare http://www.infoarena.ro/job_detail/1410636

Testele la aceasta problema nu acopera toate cazurile posibile. Majoritatea surselor evaluate la 100 sunt gresite. Contraexemplu la sursa mea de 100:

6
0.0 0.0
1.0 1.0
2.0 2.0
3.0 3.0
7.0 0.0
4.0 -2.0