Cod sursa(job #516373)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 decembrie 2010 20:36:41
Problema Triang Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define Nmax 1510
#define eps 1e-6
#define pb push_back
#define mp make_pair

#define file_in "triang.in"
#define file_out "triang.out"

#define f first
#define s second

vector< pair <double,double > > v;

double x,y;
int n;

int min(double a, double b)
{
	return (a<b && fabs(b-a)>eps);
}

int max(double a, double b)
{
	return (a>b && fabs(b-a)>eps);
}

int bs(double x, double y, int ls, int ld)
{
	int mij=(ls+ld)>>1;

	while (ls<=ld)
	{
        if (min(v[mij].f,x))
		{
			ls=mij+1;
			mij=(ls+ld)>>1;
		}
		else
		if (max(v[mij].f,x))
		{
			ld=mij-1;
			mij=(ls+ld)>>1;
		}
		else
		if (min(v[mij].s,y))
		{
			ls=mij+1;
			mij=(ls+ld)>>1;
		}
		else
		if (max(v[mij].s,y))
		{
			ld=mij-1;
			mij=(ls+ld)>>1;
		}
		else//e bun
		{
			return 1;
		}
	}

	//nu am gasit
	return 0;
}
	
	

int main()
{
	int i,j;
	double x1,x2,y3,y2,x4,y4,q;
    int nrtri=0;
    double raza,unghi;
	freopen(file_in,"r",stdin);
		
	scanf("%d", &n);
	for (i=0;i<n;++i)
	{
		scanf("%lf %lf", &x, &y);
		v.pb(mp(x,y));
	}
	fclose(stdin);
	
	sort(v.begin(),v.end());//sortam coordonatele
	
	//cautare binara
	for (i=0;i<n-1;++i)
		 for (j=i+1;j<n;++j)
		 {
			x1=v[i].f;
			x2=v[j].f;
			y3=v[i].s;
			y2=v[j].s;
			
			//un triunghi e echilateral daca toate unghiurile au 60 grade
			q=M_PI/3.0;
			unghi=atan2(y2-y3,x2-x1);
			raza=sqrt((x2-x1)*(x2-x1)+(y2-y3)*(y2-y3));
			nrtri+=bs(x1+raza*cos(unghi-q),y3+raza*sin(unghi-q),j+1,n-1);
			nrtri+=bs(x1+raza*cos(unghi+q),y3+raza*sin(unghi+q),j+1,n-1);
			
			
		 }
	freopen(file_out,"w",stdout);	 
	printf("%d", nrtri);	 
	
	fclose(stdout);
	
	return 0;
}