Cod sursa(job #58225)

Utilizator info_arrandrei gigea info_arr Data 4 mai 2007 18:34:27
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
using namespace std;

#define nmax 105
#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];
point q[nmax*nmax];

void sort()
{
  int i,j,k;
  point aux;
  for (i=1; i<=n; i++)
   {
    j=i;
    while (j/2 && (q[j].y*q[j/2].x)>(q[j].x*q[j/2].y))
     {
       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].y*q[k].x>q[k+1].x*q[k].y)) k++;
     if (q[j].y*q[k].x>q[j].x*q[k].y) break;
     aux=q[j]; q[j]=q[k]; q[k]=aux; 
     j=k;
    }
 }
}           

void calculate()
{
  int k=0,pp1=0,pp2=0;

  for (int i=1; i<n; i++)
    for (int j=i+1; j<=n; j++)
     if (p[i].x-p[j].x!=0 && p[i].y-p[j].y!=0)
     { q[++k].y=p[i].y-p[j].y; q[k].x=p[i].x-p[j].x; }
    else if (p[i].x-p[j].x==0)  pp1++;
     else pp2++;
  sol+=pp1*(pp1-1)/2+pp2*(pp2-1)/2;
  n=k;
}      

void solve()
{
 int i,j,c;
 int cr;
 i=1;
 while (i<=n)
  {
   cr=q[i].y*q[i+1].x-q[i].x*q[i+1].y;
   j=i+1;
   if ( cr==0 )
      while (q[i].y*q[j].x-q[i].x*q[j].y==0)
	{
	 j++;
	 if (j>n) { j=i+1;  break; }
	}
   else { i++; continue; }
   j--; 
   sol+=(j-i)*(j-i+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;
}