Cod sursa(job #65185)

Utilizator sealTudose Vlad seal Data 7 iunie 2007 14:37:48
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<stdlib.h>
#define Nm 1000
int X[Nm],Y[Nm],n,t;
struct pa
{
    int x,y;
} A[Nm*Nm];

void read()
{
    int i;

    freopen("trapez.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;++i)
	scanf("%d%d",X+i,Y+i);
}

int comp(pa a, pa b)
{
    if(!a.x)
	if(b.x)
	    return 1;
	else
	    return 0;
    if(!b.x)
	return -1;
    long long d=(long long)a.y*b.x-(long long)b.y*a.x;
    if((long long)a.x*b.x<0)
	d=-d;
    if(d>0)
	return 1;
    if(d<0)
	return -1;
    return 0;
}

int cmp(const void *a, const void *b)
{
    return comp(*(pa*)a,*(pa*)b);
}

void solve()
{
    int i,j,k=0;

    for(i=0;i<n;++i)
	for(j=i+1;j<n;++j)
	{
	    A[k].x=X[i]-X[j];
	    A[k++].y=Y[i]-Y[j];
	}
    qsort(A,k,sizeof(pa),cmp);

    j=1;
    for(i=1;i<k;++i)
	if(comp(A[i],A[i-1]))
	{
	    t+=j*(j-1)>>1;
	    j=1;
	}
	else
	    ++j;
    t+=j*(j-1)>>1;
}

void write()
{
    freopen("trapez.out","w",stdout);
    printf("%d\n",t);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}