Cod sursa(job #39877)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 27 martie 2007 04:11:47
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
// Problema trapez

#include <stdio.h>
#define MAX       1001

long X[MAX], Y[MAX];

int pozitie( int st, int dr )
{
    long aux;
    long piv = Y[st];
    int i, j;
    i = st-1;
    j = dr+1;
    do{
        do{ i++; }while( Y[i] < piv );
        do{ j--; }while( Y[j] > piv );
        if( i < j )
            {
                aux = Y[i];
                Y[i] = Y[j];
                Y[j] = aux;
                aux = X[i];
                X[i] = X[j];
                X[j] = aux;
            }
    }while( i<= j );
    return j;    
}

int qs( int st, int dr )
{
    if ( st == dr ) return 0;
    int m = pozitie( st, dr );
    qs( st, m );
    qs( m+1, dr );
    return 0;
}

int main()
{
    int i, n, nr;
    freopen( "trapez.in" ,"rt", stdin );
             scanf( "%d", &n );
             for( i=1; i<=n; i++ )
                  scanf( "%d %d", &X[i], &Y[i] );
    fclose( stdin );
    
    qs( 1, n );
    nr = 0;
    int j, k, l;
    for( i=1; i<n-2; i++ )
         for( j=i+1; j<n-1; j++ )
              for( k=j+1; k<n; k++ )
                   for( l=k+1; l<=n; l++ )
                        if( (Y[l] - Y[k])*(X[j]-X[i]) == (Y[j]-Y[i])*(X[l]-X[k]) ) nr++;
    
    freopen( "trapez.out", "wt", stdout );
             printf( "%d\n", nr );
    fclose( stdout );
    return 0;
}