Nu credeti ca ati exagerat putin cu limita de timp?
Nu de alta, dar nici solutia oficiala nu ia 100 de p, iar solutia mea in C++ merge mai repede (pacat ca testul 1 imi iese si mie din timp).

Am si eu o intrebare legata de modul in care au fost concepute testele.  Cum generezi un poligon convex de N puncte? Daca generezi aleator cat de multe puncte vrei si faci infasuratoarea convexa sunt prea mici sansele sa aiba 1000 puncte.

poligonul nu se autointersecteaza nu?

Ar fi interesant sa facetzi clasamente la fiecare pb cu cei mai buni timpi (ca pe sgu).

Am incercat sa rezolv problema astfel :
1.caut binar valoarea maxima ceruta (formez un graf bipartit , in prima multime = oamenii, in a doua adaposturile si introduc doar muchiile de cost  <=x la un moment dat)
2. pt acea valoare maxima fac flux maxim de cost minim.
Problema este ca pe testele de la 3 in sus mie nu imi gaseste nici prima valoare bine.
Mi se pare clara echivalenta : Daca fiecare nod din prima multime are asociat un nod din a doua multime, iar fiecare nod din a doua multime are asociat un nod din prima atunci exista un flux maxim de valoare N.

Mie in general imi merg sursele mai rapid pe C. Oricum am inteles care e ideea, cand tu calculezi coeficientii o singura data, dar mi se pare mai elegant cum fac eu si nu cred ca ar trebui sa conteze daca aleg intre lucrul cu numere reale si fara (tinand cont ca nu conteaza prea mult precizia).

din pacate nu folosesc C++ ci doar C si eu nu calculez dreapta ca ecuatie de genul ax+by+c=0 ci determin daca este deasupra sau dedesubtul ei cu produsul incrucisat (evit lucrul cu numere reale) . Asta ar trebui sa imi reduca timpul de executie nu?

Totusi  ce trebuie sa optimizez sa iau 100 ?..Testul 6 imi iese idin timp. Cautare binara facuta klumea, sursa clara, bine implementata si tot iau 90 . Mi se pare limita de timp putzin cam mica totusi.

Am si eu o intrebare de ce nu merge sa citesc cu fgets ? Am trimis sursa cu citire fgets si am luat WA pe toate testele, iar cu scanf simplu am luat 100 . [/u]

ok.. am reimplementat putin ...
Testul 6 imi da "too bad"
am testat cateva situatii particulare precum segmentele verticale,punctele de pe marginea dreapta a unei benzi, punctele de pe segmente, punctele care au abscisa mai mica/mare decat cea minima/maxima etc
daca avetzi alte situatii sau daca se poate da testul 6 v-as fi recunoscator

da..eu consideram o "banda" = dreapta  
am inteles acum, si sper sa o fac klumea
multumesc oricum

o mica intrebare referitoare la solutia publicata in articol pt 100 p
spune acolo ca noi pt fiecare din punctele poligonului formam acele benzi etc
dar daca unul din cele m puncte are o abscisa pe care nu se afla nici un punct al poligonului ?
eu am luat toate coordonatele x ale celor m puncte, dar cum era de asteptat 2 teste mi-au dat TLE si unul "Too bad!" (aici chiar nu shtiu de ce)

Pai asa il construiesc si eu!
numai ca pt a completa tot vectorul e suficient sa calculezi numai pt 22 de configuratii(fara sa te opresti cand ai gasit o configuratie care itzi convine)
00000000000001
00000000000011
00000000000111
..
11111111111111
acestea luate ca in exemplu
daca ai facut recursiv posteaza putzin functia pls

Am calculat tot vectorul la inceput !  
Toate imi ies din timp !  
Poate imi explici cum l-ai calculat mai rapid...
10x

Ok...
Am si eu o intrebare : solutia mea determina pur si simplu care jucator castiga pentru o configuratie data recursiv. Am incercat 2 cazuri : cand gasesc o solutie care ii convine primului jucator, ma opresc din alte cautari, al doilea : nu ma opresc pt ca toate configuratiile le retin intr-un vector de vreo 2^22 elemente si cand n este destul de mare unele configuratii se repeta. Va rog spuneti-mi daca exista alta solutie (totusi 3 sec timpul) sau daca trebuie sa mai optimizez ca sa imi mearga si ultimele 3 teste.
10x