Cod sursa(job #804129)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 28 octombrie 2012 21:53:35
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;

struct pct
{
	double x,y;
};

const double ep=1e-3;
const double pi=3.141592;

pct a[1501],p;
int i,j,n,nr,t;


bool cmp(pct a,pct b)
{
	return ((b.x-a.x>ep) || ((fabs(b.x-a.x)<ep) && (b.y-a.y>ep)));
}

int cautare(pct b)
{
	int m,p=1,u=n;
	while (p<=u)
	{
		m=(p+u)/2;
		if ((a[m].x-b.x<ep) && (a[m].y-b.y<ep))
			return m;
		else if (cmp(a[m],b))
			p=m+1;
		else u=m-1;
	}
	return 0;
}
	
int main()
{
	ifstream f("triang.in");
	ofstream g("triang.out");
	f >> n;
	for (i=1;i<=n;i++)
		f >> a[i].x >> a[i].y;
	sort(a+1,a+n+1,cmp);
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			p.x=a[i].x+(a[j].x-a[i].x)*cos(pi/3)-(a[j].y-a[i].y)*sin(pi/3);
			p.y=a[i].y+(a[j].x-a[i].x)*sin(pi/3)+(a[j].y-a[i].y)*cos(pi/3);
			t=cautare(p);
			if (t>j)
				nr++;
			p.x=a[i].x+(a[j].x-a[i].x)*cos(-pi/3)-(a[j].y-a[i].y)*sin(-pi/3);
			p.y=a[i].y+(a[j].x-a[i].x)*sin(-pi/3)+(a[j].y-a[i].y)*cos(-pi/3);
			t=cautare(p);
			if (t>j)
				nr++;
		}
	g << nr;
}