182 Popandai

[•domino]

Aici puteţi discuta despre problema Popandai.

[•fireatmyself]

am implementat o sursa in care imi da batai de cap urmatorul fragment cod:

Cod:

  for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                for (k = j+1; k < N; k++)
                {
                        x=Under[i][k]-Under[i][j]-Under[j][k]-1;
                        y=Under[i][j]+Under[j][k]-Under[i][k];
                        if ( ((P[j].x*a+P[j].y*b+c)<0) )  Down[ x ] = MAX(arie(i,j,k),Down[ x ]);
                        else Up[ y ] = MAX(arie(i,j,k),Up[ y ]);
                }

unde a,b,c sunt coieficentii dreptei formate de pct i (considerat pct cu cel mai mic x) si k (considerat pct cu cel mai mare x), iar Under[ a ][ b ] = nr de pct de sub segmentul [a,b] (ca indici).
problema este ca la un moment dat fie x, fie y imi dau negative (adica ajung sa am nr < 0 de pct in interiorul unui triunghi). am consultat si solutia oficiala, dar nu vad vreo diferenta... ma poate ajuta cineva ?


L.E. : am luat 100. consideram ca aria minima se obtine doar daca am fix K puncte in interior, iar daca mai adaug unul sigur v-a creste aria. m-am inselat. multumesc lui Adrian Airinei pentru ca m-a descurcat