Cod sursa(job #426206)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 26 martie 2010 16:30:04
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct panta
{
	int x,y;
};
panta m[1<<20];
int q,n,x[1<<10],y[1<<10];
long long nrp,nrt,nrap;
int cmmdc(int x,int y)
{
	int r=x%y;
	while(r)
	{
		x=y;
		y=r;
		r=x%y;
	}
	return y;
}
int cmmmc(int x,int y)
{
	return x/cmmdc(x,y)*y;
}
bool comp(const panta &A,const panta &B)
{
	int qq=cmmmc(A.x,B.x);
	if(A.y*(qq/A.x)>B.y*(qq/B.x))
			return false;
	return true;
}
int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(x[i]==x[j])
				nrp++;
			else
			{
				++q;
				m[q].x=x[i]-x[j];
				m[q].y=y[i]-y[j];
			}
	sort(m+1,m+q+1,comp);
	panta term;
	term.x=m[1].x;
	term.y=m[1].y;
	nrap=1;
	for(int i=2;i<=q;i++)
		if(term.y*m[i].x==term.x*m[i].y)
			nrap++;
		else
		{
			nrt+=nrap*(nrap-1)/2;
			nrap=1;
			term.x=m[i].x;
			term.y=m[i].y;
		}
	nrt+=nrap*(nrap-1)/2;
	nrt+=nrp*(nrp-1)/2;
	printf("%lld",nrt);
	return 0;
}