Cod sursa(job #577700)

Utilizator CS-meStanca Marian Ciprian CS-me Data 10 aprilie 2011 15:15:12
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
#include<stdlib.h>
FILE *fin=fopen("trapez.in","r");
FILE *fout=fopen("trapez.out","w");
long int n,i,j,k;
long long nra,nrb,nr;

struct puncte{
	long long a,b;
} v[1001],pnt[500000];


int cmp(const void *a, const void *b){
long long c;

	c=(*(puncte *)a).a*(*(puncte *)b).b - (*(puncte *)a).b*(*(puncte *)b).a;

	if(c<0){
		return -1;
	}
	if(c>0){
		return 1;
	}

return 0;
}


int main(){

	fscanf(fin,"%ld",&n);

	for(i=1;i<=n;i++){
		fscanf(fin,"%lld %lld",&v[i].a ,&v[i].b);
	}

	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			if(v[i].a==v[j].a){
				nra++;
			}
			else
			if(v[i].b==v[j].b){
				nrb++;
			}
			else{
				k++;
				pnt[k].a=v[i].b-v[j].b;
				pnt[k].b=v[i].a-v[j].a;

				if(pnt[k].b<0){
					pnt[k].b*=-1;
					pnt[k].a*=-1;
				}
			}
		}
	}

	qsort(pnt+1,k,sizeof(puncte),cmp);
	int ok=0;
	for(i=1;i<=k;i++){
		j=i+1;
		ok=0;
		while( pnt[i].a*pnt[j].b==pnt[i].b*pnt[j].a && j<=k){
			j++;
			ok=1;
		}
		nr=nr+ok*(j-i)*(j-i-1)/2;

		i=j-1;
	}

 //	nr=nr*(nr-1)/2;

	nr+=nra*(nra-1)/2+nrb*(nrb-1)/2;


	fprintf(fout,"%lld",nr);

	fclose(fout);
	fclose(fin);

return 0;
}