Cod sursa(job #286246)

Utilizator floringh06Florin Ghesu floringh06 Data 23 martie 2009 16:55:11
Problema Trapez Scor 100
Compilator cpp Status done
Runda qwerty-1 Marime 1.64 kb
using namespace std;   
  
#define nmax 1005   
#define eps 0.0000000001   
#include<stdio.h>   
  
FILE *fin=fopen("trapez.in","r"),   
     *fout=fopen("trapez.out","w");   
  
struct point   
{   
  int x,y;   
};   
  
int n,sol;   
point p[nmax];   
long double q[nmax*nmax];   
  
void sort()   
{   
  int i,j,k;   
  long double aux;   
  for (i=1; i<=n; i++)   
   {   
    j=i;   
    while (j/2 && q[j]-q[j/2]>eps)   
     {   
       aux=q[j/2];   
       q[j/2]=q[j];   
       q[j]=aux;   
       j/=2;   
      }   
   }   
i=n;   
while (i>1)   
 {   
   aux=q[1];   
   q[1]=q[i];   
   q[i]=aux;   
   i--; j=1;   
   while (1)   
    {   
     k=2*j;   
     if (k>i) break;   
     if (k+1<=i && q[k+1]-q[k]>eps) k++;   
     if (q[j]-q[k]>eps) break;   
     aux=q[j]; q[j]=q[k]; q[k]=aux;    
     j=k;   
    }   
 }   
}              
  
void calculate()   
{   
  int k=0,pp=0;   
  
  for (int i=1; i<n; i++)   
    for (int j=i+1; j<=n; j++)   
      if (p[i].x-p[j].x!=0) q[++k]=double(p[i].y-p[j].y)/(p[i].x-p[j ].x);   
       else pp++;   
  sol+=(pp*(pp-1))/2;   
  n=k;   
}         
  
void solve()   
{   
 int i,j,c;   
 long double cr;   
 i=1;   
 while (i<=n)   
  {   
   cr=q[i]; j=i;   
   while (q[j]==cr) j++;   
   j--; c=j-i;   
   sol+=(c*(c+1))/2;   
   i=j+1;   
  }     
}   
  
int main()   
{   
    fscanf(fin,"%d",&n);   
    for (int i=1; i<=n; i++)   
     fscanf(fin,"%d%d\n",&p[i].x,&p[i].y);   
    calculate();   
    sort();   
    solve();   
    fprintf(fout,"%d\n",sol);   
fclose(fin);   
fclose(fout);   
return 0;   
}