Cod sursa(job #383600)

Utilizator ionutz32Ilie Ionut ionutz32 Data 17 ianuarie 2010 11:04:11
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
struct punct
{
	int x,y;
};
struct muchie
{
	int x,y;
};
punct v[1005],pct1,pct2,pct3,pct4;
muchie a[1000005];
int n,i,j,x,y,m,cadran,vechi,xv,yv,nr1,nr2,aux,k;
double dify1,difx1,dify2,difx2;
long long sol;
bool ok;
struct cmp
{
	bool operator()(const muchie &m1,const muchie &m2)const
    { 
		if (v[m1.x].y<v[m1.y].y)
		{
			pct1=v[m1.x];
			pct2=v[m1.y];
		}
		else
		{
			pct1=v[m1.y];
			pct2=v[m1.x];
		}
		if (v[m2.x].y<v[m2.y].y)
		{
			pct3=v[m2.x];
			pct4=v[m2.y];
		}
		else
		{
			pct3=v[m2.y];
			pct4=v[m2.x];
		}
		dify1=pct2.y-pct1.y;
		dify2=pct4.y-pct3.y;
		if (pct1.x<pct2.x)
			difx1=pct2.x-pct1.x;
		else
			difx1=pct1.x-pct2.x;
		if (pct3.x<pct4.x)
			difx2=pct4.x-pct3.x;
		else
			difx2=pct3.x-pct4.x;
		if (pct2.x<pct1.x && pct4.x<pct3.x)
			if (dify1/difx1>dify2/difx2)
				return 0;
			else
				return 1;
		else
			if (pct2.x>pct1.x && pct4.x>pct3.x)
				if (dify1/difx1>dify2/difx2)
					return 1;
				else
					return 0;
			else
				if (pct2.x<pct1.x && pct4.x>pct3.x)
					return 1;
				else
					if (pct2.x>pct1.x && pct4.x<pct3.x)
						return 0;
					else
						if (pct2.x==pct1.x)
							return 0;
						else
							if (pct3.x==pct4.x)
								return 1;
							else
								if (pct1.y==pct2.y)
									return 1;
								else
									return 0;
    }
};
int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		scanf("%d %d",&v[i].x,&v[i].y);
	for (i=1;i<n;++i)
		for (j=i+1;j<=n;++j)
		{
			++m;
			a[m].x=i;
			a[m].y=j;
		}
	sort(a+1,a+m+1,cmp());
	for (i=1;i<=m;++i)
	{
		if (v[a[i].x].y>v[a[i].y].y)
		{
			pct1=v[a[i].y];
			pct2=v[a[i].x];
		}
		else
		{
			pct1=v[a[i].x];
			pct2=v[a[i].y];
		}
		if (pct2.x<pct1.x)
			cadran=2;
		else
			cadran=1;
		x=abs(pct1.x-pct2.x);
		y=pct2.y-pct1.y;
		nr1=x;
		nr2=y;
		while (nr2)
		{
			aux=nr1;
			nr1=nr2;
			nr2=aux%nr2;
		}
		x=x/nr1;
		y=y/nr1;
		if (cadran==vechi)
		{
			if (x==xv && y==yv)
				ok=true;
			else
				ok=false;
		}
		else
			ok=false;
		if (ok)
			++k;
		else
		{
			sol+=(k-1)*k/2;
			xv=x;
			yv=y;
			vechi=cadran;
			k=1;
		}
	}
	printf("%lld",sol+(k-1)*k/2);
	return 0;
}