Cod sursa(job #426198)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 26 martie 2010 16:09:51
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct panta
{
	int x,y;
};
panta m[1<<20];
int q,n,nrt,nrap,x[1<<10],y[1<<10],nrp[1<<10];
bool f[1<<10][1<<10];
bool comp(const panta &A,const panta &B)
{
	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++)
	{
		f[i][i]=true;
		for(int j=i+1;j<=n;j++)
			if(x[i]==x[j])
			{
				nrp[i]++;
				f[i][j]=f[j][i]=true;
			}
			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;
	for(int i=1;i<=n;i++)
	{
		int suma=0;
		for(int j=1;j<=n;j++)
			if(f[i][j]==false)
				suma+=nrp[j];
		nrt+=suma*nrp[i];
	}
	printf("%d",nrt);
	return 0;
}