Triangulatii!

[•chera_lary]

Salut!
Vreau sa imi prezentati, daca se poate, o metoda de afisare a triangulatiilor unui patrulater convex!
Numarul lor il pot afla din formula lui Catalan!
Va multumesc!

[•filipb]

Poti folosi metoda backtracking.
Poti face asa: consideri un vector st in care st_i reprezinta celalalt capat al diagonalei care contine varful i din poligon sau 0, daca din varful i nu pleaca nicio diagonala. Poti impune i < st_i. Conditia ca 2 diagonale (i st_i) (j st_j) sa nu se intersecteze este ca i <= j, st_j <= st_i sau j <= i, st_i <= st_j.

[•chera_lary]

Structura(algoritmul) backtracking o(il) stiu, dar as vrea sa vad codul functiei valid .
Multumesc pentru informatii!

[•filipb]

Stai ca nu merge cum spuneam mai sus ca pot fi mai multe diagonale care pleaca din acelasi varf . Cel mai simplu este sa consideri toate diagonalele si la fiecare pas verifici daca poti sau nu sa pui diagonala curenta:

Cod:

#include <stdio.h>

typedef struct { int x, y; } diagonala;

int N;
diagonala D[1024]; int nr_diagonale;

int st[1024]; // st[i] = 1 <=> am selectat diagonala i

int between(int x, int r1, int r2)
{ return (r1 <= x && x <= r2); }

int intersect(int i1, int i2)
{
    return (D[i1].x != D[i2].x && D[i1].x != D[i2].y && D[i1].y != D[i2].x && D[i1].y != D[i2].y &&
            between(D[i1].x, D[i2].x, D[i2].y) + between(D[i1].y, D[i2].x, D[i2].y) == 1);
}

void back(int nivel)
{
    int i;

    if (nivel == nr_diagonale + 1)
    {
        int j = 0;
        for (i = 1; i <= nr_diagonale; ++i)
            j += st[i];
            
        if (j == N-3) // daca am selectat N-3 diagonale afisam
        {
            for (i = 1; i <= nr_diagonale; ++i)
                if (st[i])
                    printf("(%d %d) ", D[i].x, D[i].y);
            printf("\n");
        }
        
        return ;
    }

    st[nivel] = 0; back(nivel+1); // nu selectam diagonala

    // verificam daca putem sa o selectam
    if (st[1] && nivel == 2)
        i = 0;

    for (i = 1; i < nivel; ++i)
        if (st[i] && intersect(i, nivel))
            return ;
    st[nivel] = 1; back(nivel+1);
}

int main(void)
{
    int i, j;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d", &N);
    
    for (i = 1; i <= N; ++i)
        for (j = i+1; j <= N; ++j)
        {
            if (i+1 == j || (i == 1 && j == N)) continue;
            ++nr_diagonale;
            D[nr_diagonale].x = i;
            D[nr_diagonale].y = j;
        }

    i = intersect(2, 3);
    back(1);
        
    return 0;
}

Sunt multe optimizari care pot fi facute si poti imbunatati programul de mai sus.

Functia valid la care te referi poate fi ceva de genul:

Cod:

int between(int x, int r1, int r2)
{ return (r1 <= x && x <= r2); }

int intersect(int i1, int i2)
{
    return (D[i1].x != D[i2].x && D[i1].x != D[i2].y && D[i1].y != D[i2].x && D[i1].y != D[i2].y &&
            between(D[i1].x, D[i2].x, D[i2].y) + between(D[i1].y, D[i2].x, D[i2].y) == 1);
}

int valid()
{
int i;
for (i = 1; i < nivel; ++i)
   if (st[i] && intersect(i, nivel))
       return 0;
return 1;
}