Cod sursa(job #426207)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 26 martie 2010 16:32:17
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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;
bool comp(const panta &A,const panta &B)
{
	if((A.x<0 && B.x<0) || (A.x>0 && B.x>0))
	{
		if(A.y*B.x>A.x*B.y)
			return false;
	}
	else if(A.x<0 || B.x<0)
	{
		if(A.y*B.x<A.x*B.y)
			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;
}