Cod sursa(job #255150)

Utilizator DraStiKDragos Oprica DraStiK Data 8 februarie 2009 18:53:35
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#define DIM 1001005
#define INF 1LL<<60
struct trpz {long long s,j;} a[DIM],v[DIM/1000];
int n,m;
long long nrt=1;
void read ()
{
	int i;
	scanf ("%d",&n);
	for (i=1; i<=n; ++i)
		scanf ("%lld%lld",&v[i].s,&v[i].j);
}
void panta ()
{
	int i,j;
	for (i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			a[++m].s=v[j].j-v[i].j;
			a[m].j=v[j].s-v[i].s;
			if (a[m].j==0)
				a[m].j=INF;
		}
}
int cmp (trpz a,trpz b)
{
	int c,d,ok=0;
	c=a.s*b.j;
	d=a.j*b.s;
	if (a.j<0)
		++ok;
	if (b.j<0)
		++ok;
	if (ok!=1)
	{
		if (c<d)
			return -1;
		if (c>d)
			return 1;
		return 0;
	}
	if (c<d)
		return 1;
	if (c>d)
		return -1;
	return 0;

}
void qsort (int st,int dr)
{
	int i=st,j=dr;
    trpz piv=a[(st+dr)/2],aux;
    do
    {
        while (cmp (a[i],piv)<0) 
            ++i;
        while (cmp (a[j],piv)>0) 
            --j;
        if (i<=j)
        {
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
            ++i; 
            --j;    
        }
    } 
    while (i<=j);
    if (st<j)
        qsort(st,j);
    if (i<dr) 
        qsort(i,dr);    
}
void solve ()
{
    int i,nr;
	for (i=1; i<m; )
	    if (!cmp (a[i],a[i+1]))
	    {
            nr=1;
			while (!cmp (a[i],a[i+1]) && i<=m)
            {
                ++i;
                ++nr;
            }
			nrt*=(nr-1)*nr/2;
        }          
        else
            ++i; 
		printf ("%lld",nrt);
}
int main ()
{
    freopen ("trapez.in","r",stdin);
    freopen ("trapez.out","w",stdout);    
    read ();
    panta ();
    qsort (1,m);
	solve ();
    return 0;
}