Cod sursa(job #826760)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 1 decembrie 2012 10:53:53
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>
using namespace std;

struct pct
{
	int x,y;
};

pct v[300],p;
int a[300][300],i,j,k,n;
long long s,t;

int arie(pct a,pct b,pct c)
{
	long long s;
	s=a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
	if (s>0)
		return 0;
	else if (s<0)
		return 1;
	else return -1;
}

int main()
{
	ifstream f("patrulatere.in");
	ofstream g("patrulatere.out");
	f >> n;
	for (i=1;i<=n;i++)
		f >> v[i].x >> v[i].y;
	s=n*(n-1)*(n-2)*(n-3)/24;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if ((v[i].y<=v[j].y) && (i!=j))
				for (k=1;k<=n;k++)
					if ((k!=i) && (k!=j) && (v[i].y<=v[k].y) && (v[k].y<=v[j].y))
					{
						p.x=v[i].x+1;
						p.y=v[i].y;
						if ((arie(v[i],v[j],v[k])+arie(v[i],v[j],p)==1))
						{
							a[i][j]++;
							a[j][i]++;
						}
					}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if ((i!=j) && (v[i].y==v[j].y) && (v[j].x<v[i].x))
				a[i][i]++;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if ((v[i].y<=v[j].y) && (i!=j))
				for (k=1;k<=n;k++)
					if ((k!=i) && (k!=j) && (v[i].y<=v[k].y) && (v[k].y<=v[j].y))
					{
						p.x=v[i].x+1;
						p.y=v[i].y;
						if ((arie(v[i],v[j],v[k])+arie(v[i],v[j],p)==1))
							t+=a[i][j]-a[i][k]-a[j][k]+a[k][k]-1;
						else 
						{
							if ((v[i].y!=v[k].y) && (v[j].y!=v[k].y))
								t+=a[i][k]+a[j][k]-a[i][j]-a[k][k];
						}
					}
	g << s-t;
	return 0;
}