Cod sursa(job #157588)

Utilizator cos_minBondane Cosmin cos_min Data 13 martie 2008 09:44:48
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#define in "trapez.in"
#define out "trapez.out"
#define eps 1e-14
#include <math.h>

struct Punct{
    int x, y;
}a[1000000], l[1000000];

int m=0;
int i, n, j, k, t, r, u;
int rest, cmmd, select[1000000];
double sir[1000000];
int sol = 0;

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

void Read();
void Panta();
void Quick(int st, int dr);
void Write();
int Numar(int n);
int Facto(int k);
int Cmmdc(int a, int b);
void Solve();

int main()
{
    Read();
    Panta();
    Quick(1,m);
    Solve();
    
	return 0;
}

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

void Panta()
{
      r = 0;
      sol = 0;
      for (int i = 1; i < n; i++ )
      {
		 for (int j = i+1; j <= n; j++ )
		 { 
		     int t,u;
		     t = a[j].y - a[i].y;
             u = a[j].x - a[i].x;
             if ( u == 0 ) 
             {
                 r++;
             }    
             else
             {
                 ++m;
                 sir[m] = (double)t/u;
             }    
         }
      } 
      //sol += r*(r-1)/2;
}

void Quick(int st, int dr)
{
    int i = st-1, j = dr+1; 
    double pivot = sir[st], aux;
	do
	{
	    do { i++; } while ( pivot - sir[i] > eps );
	    do { j--; } while ( sir[j] - pivot > eps );
		if ( i <= j )
		{
			aux = sir[i];
			sir[i] = sir[j];
			sir[j] = aux;
		}
	}
	while ( i <= j );

	if ( st < j ) Quick(st, j);
	if ( i < dr ) Quick(i, dr);
}    

void Solve()
{
	int r , k, i = 1;
	while ( i < m )
	{
	    r = 1;
	    k = 1;
	    if ( fabs(sir[i]-sir[i+1]) < eps )
	    {
	        int j = i+1;
	        while ( fabs(sir[i]-sir[j]) < eps )
            {
	            r++;
	            j++;
	        }
	        k = j - i;
         }
         i += k;
         sol += r*(r-1)/2;
     }      
     /* for ( int i = 1; i <= m; i++ ) 
      fprintf(fout,"%f ", sir[i]);   */
   fprintf(fout,"%d",sol); 
   fclose(fout);
} 

int Cmmdc(int a, int b)
{ 
    if ( b == 0 ) return a;
    return Cmmdc(b, a%b);
}