Cod sursa(job #255170)

Utilizator DraStiKDragos Oprica DraStiK Data 8 februarie 2009 19:07:49
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <cmath>

using namespace std;

#define dim 500001

#define input  "trapez.in"
#define output "trapez.out"

ifstream fin (input);
ofstream fout(output);

struct punct
{
    long x, y;
} ;   

long n, i, j, m, k, nr_trapez;

punct puncte[1001], aux;
punct pante[dim];
void quick(long li, long ls);
void poz (long li, long ls, long&k );


int main()
{
    fin >> n;
    
    for ( i = 1; i <= n; i ++ )
    
        fin >> puncte[i].x >> puncte[i].y;
        
    // calculam pantele
        
    for ( i = 1; i < n; i ++ )        
    
        for ( j = i + 1; j <= n; j ++ )
        {
                m ++; 
                pante[m].x = (puncte[j].x-puncte[i].x);
                pante[m].y = (puncte[j].y-puncte[i].y);
        }
     
    quick(1,m);	
    
    i = 1;        
    
    while ( i <= m - 1)
    {
        j = i + 1;
        
        while ( (j <= m) && (pante[i].y*pante[j].x == pante[j].y*pante[i].x) )
        
                j ++;
        
        long v = j - i;        
          
      // fout << v << " ";                        
                                                                            
        if ( v > 1 )
        
                nr_trapez += ((v)*(v-1) / 2);
      
        i = j;
    }                                          
    
     fout << nr_trapez;                              
                                                                                  
	return 0;
}
        
                                
void quick(long li, long ls)
{
    if ( li < ls )
    {
        poz(li, ls, k);
        quick(li, k-1);
        quick(k+1, ls);       
    }       
}
    
void poz (long li, long ls, long&k)

{
    int i = li, j = ls, i1 = 0, j1 = -1, c;
    while ( i < j )
    {
        if ( pante[i].y*pante[j].x > pante[j].y*pante[i].x )
        {
            aux = pante[j]; pante[j] = pante[i]; pante[i] = aux;
            c = i1;
            i1 = -j1; j1 = -c;
        }
        i += i1;
        j += j1;
    }
    k = i;
}