Cod sursa(job #184805)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 24 aprilie 2008 12:41:23
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#define M 500

long long sol[M][2],x[1001],y[1001],j,i,nr,q,ss,suma;
int n;

void qsort(long long l,long long r)
{long long i,j,x,y;
     i=l;j=r;x=(l+r)/2;
     do
     {
		       while ((long long)sol[i][0]*sol[x][1]<(long long)sol[i][1]*sol[x][0])
				i++;
		       while ((long long)sol[j][0]*sol[x][1]>(long long)sol[j][1]*sol[x][0])
				j--;
		       if (i<=j)
		       {
				  y=sol[i][0];sol[i][0]=sol[j][0];sol[j][0]=y;
				  y=sol[i][1];sol[i][1]=sol[j][1];sol[j][1]=y;
				  i++;j--;
		       }
     }
     while (i<=j);
     if (i<r) qsort(i,r);
     if (l<j) qsort(l,j);
}

void bsort()
{long long y;
     for (i=1;i<q;i++)
         for (j=i+1;j<=q;j++)
             if ((long long)sol[i][0]*sol[j][1]>(long long)sol[i][1]*sol[j][0])
             {
                      y=sol[i][0];sol[i][0]=sol[j][0];sol[j][0]=y;
                      y=sol[i][1];sol[i][1]=sol[j][1];sol[j][1]=y; 
             }
}

int main()
{
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
		      scanf("%lld %lld",&x[i],&y[i]);
		      for(j=1;j<i;j++)
		      {
				      q++;
				      sol[q][0]=y[i]-y[j];
				      sol[q][1]=x[i]-x[j];
				      if (sol[q][1]<0)
				      {
					     sol[q][1]=-sol[q][1];
					     sol[q][0]=-sol[q][0];
				      }
					if (sol[q][1]==0)
						if (sol[q][0]<0)sol[q][0]=-sol[q][0];
					if (sol[q][0]==0)
						if (sol[q][1]<0)sol[q][1]=-sol[q][1];
		      }
    }
    /*qsort(1,q);*/
    bsort();
    for(i=1;i<q;i++)
    {
		    j=i;
		    while (sol[j][0]*sol[j+1][1]==sol[j][1]*sol[j+1][0] && j<q)
			  j++;
		    ss=j-i+1;
		    suma+=ss*(ss-1)/2;
		    i=j;
    }

    printf("%lld\n",suma);
    return 0;
}