Cod sursa(job #359518)

Utilizator ZillaMathe Bogdan Zilla Data 27 octombrie 2009 12:11:48
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>

#define Nmax 10

struct punct{
    int x,y;
};

struct per{
    int x,y;
    double panta;
};

per b[Nmax*Nmax];
punct p[Nmax];
int n;

void qsort(int st,int dr)
{
    int i=st,j=dr;
    double mid=b[(st+dr)/2].panta;
    per tmp;
    do
        {
            while(b[i].panta<mid) ++i;
            while(b[j].panta>mid) --j;
            if(i<=j)
                {
                    tmp=b[i];
                    b[i]=b[j];
                    b[j]=tmp;
                    ++i;
                    --j;    
                }
        }while(i<=j);
        
    if(i<dr)    qsort(i,dr);
    if(j>st)    qsort(st,j);
}

int main()
{
    int i,cnt=0,j;
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d%d",&p[i].x,&p[i].y);
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
			{
				if(p[j].x-p[i].x)
					{
						b[++cnt].panta=(double)( (double)(p[j].y-p[i].y)/(double)(p[j].x-p[i].x));
						b[cnt].x=i;
						b[cnt].y=j;
					}
            }    
    qsort(1,cnt);
    
    i=1;
    j=i;
    long long rez=0;
    while(i<n)
        {
            while(b[j].panta==b[i].panta && j<=n)
                ++j;
            rez+=(long long)((j-i)*(j-i-1)/2);
            i=j; 
        }
    printf("%lld",rez);
    return 0;    
}