Cod sursa(job #14500)

Utilizator MihaiT_testTabara Mihai Test MihaiT_test Data 9 februarie 2007 10:53:31
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
using namespace std;

#define in "trapez.in"
#define out "trapez.out"
#define NMAX 1001

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

int n, ind;
LI sol;
struct Pant {
       LI sus;
       LI jos;
} panta[NMAX], axu;

LI Comb( LI i );

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

void Read();
void Solve();
void QSort(LI,LI);

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

int main()
{
    Read();
    Solve();
    
    fprintf( fout, "%d\n", sol );
    fclose( fout );
    return 0;
}

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

void Solve()
{
     int i, j, nr = 0;
     for ( i = 1; i < n; ++i )
     {
         for ( j = i + 1; j <= n; ++j )
         {
             panta[++ind].jos = abs( a[i].x - a[j].x );
             panta[ind].sus = abs( a[i].y - a[j].y );
         }
     }
     QSort( 1, ind );
     /*for ( i = 1; i <= ind; ++i )
         fprintf( fout, "%ld / %ld\n", panta[i].sus, panta[i].jos );*/
     for ( i = 1; i <= ind; ++i )
     {
         nr = 0;
         for ( j = i+1; j <= ind; ++j )
         {
             
             if ( panta[i].sus *panta[j].jos == panta[i].jos * panta[i].sus )
             {
                  nr++;
             }
         }
         sol += Comb( nr );
     }        
         
}
     
void QSort( LI st, LI dr )
{
     LI pivot = panta[st].sus;
     LI i = st - 1, j = dr + 1;
     do
     {
          do { i++; } while ( panta[i].sus < pivot );
          do { j--; } while ( panta[j].sus > pivot );
          if ( i <= j ) 
          {
               axu = panta[i];
               panta[i] = panta[j];
               panta[j] = axu;
          }
     } while ( i <= j );
     if ( i < dr ) QSort( i, dr );
     if ( st < j ) QSort( st, j );
}