Cod sursa(job #261943)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 18 februarie 2009 21:26:26
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <stdlib.h>
struct punct
{
	int x,y;
};
struct panta
{
	int a,b;
};
int n,r=0;
punct v[1005];
panta numar[1000000];
void read()
{
	int i;
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%d %d",&v[i].x,&v[i].y);
}
int cmmdc(int x,int y)
{
	int r=x%y;
	while(r)
	{
		x=y;
		y=r;
		r=x%y;
	}
	return y;
}
void solve()
{
	int i,j,trapeze=0,t,k,l,impartitor;
	for (i=1; i<=n-1; i++)
		for (j=i+1; j<=n; j++)
		{
			k=v[i].y-v[j].y;
			l=v[i].x-v[j].x;
			if (k && l)
				impartitor=cmmdc(k,l);
			else
				impartitor=1;
			numar[++r].a=k/impartitor;
			numar[r].b=l/impartitor;
			//printf("%d ",r);
		}
}
int compar(const void*p,const void *q)   
{   
    panta x=*(panta*)p,y=*(panta*)q;   
    if(x.a<y.a)   
        return -1;   
    if(x.a>y.a)   
        return 1;   
    if(x.b<y.b)   
        return -1;   
    if(x.b>y.b)   
        return 1;   
    return 0;   
}   
void sortare()
{
	qsort(numar+1,r,sizeof(numar[0]),compar);
}
void verificare()
{
	int i;
	for (i=1; i<=r; i++)
		printf("%d %d\n",numar[i].a,numar[i].b);
}
void solve2()
{
	int i,trapeze=0,j,poz=1,temp;
	while (poz!=n)
	{
		temp=0;
		for (i=poz; i<=r; i++)
			if ((numar[poz].a==numar[poz+1].a && numar[poz].b==numar[poz+1].b) || (numar[poz].a==0 && numar[poz+1].a==0) || (numar[poz].b==0 && numar[poz+1].b==0))
			{
				temp++;
				poz=i;
			}
			else
			{
				poz+=1;
				break;
			}
		trapeze+=temp*(temp-1)/2;
	}
	//for (i=1; i<=r-1; i++)
	//	if ((numar[i].a==numar[i+1].a && numar[i].b==numar[i+1].b) || (numar[i].a==0 && numar[i+1].a==0) || (numar[i].b==0 && numar[i+1].b==0))
	//		trapeze++;
	printf("%d",trapeze);
}
int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	read();
	solve();
	sortare();
	solve2();
	//verificare();
	return 0;
}