Cod sursa(job #20743)

Utilizator Pharaoh****** Pharaoh Data 21 februarie 2007 23:59:06
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>

#define lim 99999999

int a[1001][3],n,h;
long double e[500501];
unsigned long long rez=0;

void read(){
	freopen("trapez.in","r",stdin);

    scanf("%d",&n);
    int i;

    for(i=1;i<=n;i++){ scanf("%d",&a[i][1]);
					   scanf("%d",&a[i][2]); }
}

void facere(){
	int i,j;

    for(i=1;i<=n-1;i++)
    	for(j=i+1;j<n;j++)
        	if ((a[j][2]-a[i][2])==0) e[++h]=0;
            else
              if ((a[j][1]-a[i][1])==0) e[++h]=lim;
              else e[++h]=(a[j][2]-a[i][2])/(a[j][1]-a[i][1]);

}

int pivot(int st,int dr){
	int i=st,j=dr,t=0;
	long double aux;

    while(i<j){
    	if (e[i]>e[j]){
              aux=e[i]; e[i]=e[j]; e[j]=aux;
              if (t)t=0;
              else t=1;
		}

        if (t)j--;
        else i++;
	}

    return i;
}

void quick(int st,int dr){
	int p;

    if (st<dr){
    	p=pivot(st,dr);
        quick(st,p-1);
        quick(p+1,dr);
	}
}

void baga(){
	int i,r;

	r=1;
    for(i=2;i<=h;i++){
    	if (e[i]==e[i-1]) r++;
        else{ rez+=((r-1)*r)/2; r=1; }
	}
    rez+=((r-1)*r)/2;
}

void baga2(){
	int i,r;
	for(i=1;i<=h-1;i++)
		if (e[i]==e[i+1]) rez++;
}

void write(){
	freopen("trapez.out","w",stdout);

    printf("%Lu\n",rez);
}

int main(){
	read();
    facere();
    quick(1,h);
    baga2();
    write();
	return 0;
}