Cod sursa(job #14504)

Utilizator MihaiT_testTabara Mihai Test MihaiT_test Data 9 februarie 2007 10:55:32
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
//10 puncte
#include <fstream>
#include <cmath>
using namespace std;

#define in "trapez.in"
#define out "trapez.out"
#define NMAX 1001
#define eps 1e-14

typedef long int LI;
struct Punct {
       LI x;
       LI y;
} a[NMAX], aux;

double pante[NMAX*NMAX];
LI n, ind, sol, nr, num[NMAX*NMAX];

FILE *fout = fopen( out, "w" );


LI Comb( LI i );
void Read();
void Geom();
void QSort(LI,LI);

LI Comb( LI i )
{
         LI prod = 1;
         prod = i*(i-1)/2;//e numar par 
         return prod;
}

int main()
{
    Read();
    Geom();
    
    /*LI i;
    for ( i = 1; i <= ind; fprintf( fout, "%.6lf ", pante[i++] ) );*/
    fprintf( fout, "%ld\n", sol );
     
    fclose( fout );
    return 0;
}

void Read()
{
     FILE*fin = fopen( in, "r" );
     fscanf( fin, "%ld", &n );
     LI i;
     for ( i = 1; i <= n; ++i )
     {
         fscanf( fin, "%ld%ld", &a[i].x, &a[i].y );
     }
     fclose( fin );
}

void Geom()
{
     LI i, j;
     double fact;
     ind = 0;
     LI sus, jos;
     for ( i = 1; i <= n-1; ++i )
     {
         for ( j = i + 1; j <= n; ++j )
         {
             if ( i != j )
             {
                  sus = ( a[j].y - a[i].y );
                  jos = ( a[j].x - a[i].x );
                  if ( jos != 0  ) 
                  { 
                      ind++;
                      fact = (double)(sus)/(jos);
                      pante[ind] = fact;
                  }
                
             }
         }
     }
     QSort(1,ind);
     sol = 0;
     LI q = 1;
     for ( i = 1; i <= ind; ++i )
     {
         if ( fabs(pante[i] - pante[i+1]) < eps ) num[q]++;
         else
         {
             q++;
             num[q] = 1;
         }
     }
     for ( i = 0; i <= q; ++i )
         if ( num[i] > 1 )
         {
              sol += Comb( num[i] );
         }    
}  
             
void QSort( LI st, LI dr )
{
     double pivot = pante[st];
     LI i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( pante[i] < pivot );
         do { j--; } while ( pante[j] > pivot );
         if ( i <= j ) 
         {
              double aux = pante[i];
              pante[i] = pante[j];
              pante[j] = aux;
         }
     } while ( i <= j );
     if ( i < dr ) QSort( i, dr );
     if ( st < j ) QSort( st, j );
}