029 Infasuratoare convexa

[•Dante]

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

[•addy01]

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

[•Dddarius95]

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

Esti sigur ca erau in ordine trigonometrica?

Pe urmatoarele H linii se vor gasi cele H puncte ce alcatuiesc poligonul, in ordine trigonometrica.

[•thebest001]

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

[•mateidanut]

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

[•alexneki]

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