Cod sursa(job #57873)

Utilizator info_arrandrei gigea info_arr Data 3 mai 2007 12:11:50
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
using namespace std;

#define nmax 1005
#define eps 0.00001
#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];
double q[nmax*nmax];

void sort()
{
  int i,j,k;
  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;
 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;
}