Cod sursa(job #324700)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 16 iunie 2009 22:12:26
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 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;
double x1,x2,xx1,xx2,xx3,xx4,y3,y2,yy1,yy2,delta,m,d;
int nrtri;
double raza,unghi,q1,q2,q,q3,q4;

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;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=0;i<n;++i)
	{
		scanf("%lf %lf", &x, &y);
		v.pb(mp(x,y));
	}
	
	sort(v.begin(),v.end());//soratam coordonatele
	
	//for (i=0;i<n;++i)
		// printf("%.lf %.lf\n", v[i].f, v[i].s);
	
	//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;
			
			/*d=sqrt((x1-x2)*(x1-x2)+(y3-y2)*(y2-y2));
			
			/////ecuatie de gradul 2
			//delta=64*y3*y3-4*d*d*d*d*4+4*d*d*y3*y3;
			delta=64*y3*y3-16*d*d*d*d+16*y3*y3;
			yy1=(-8*y3+sqrt(delta))/8;
			yy2=(-8*y3-sqrt(delta))/8;
			
			//cazul 1
			m=-2*yy1*y3-yy1*yy1-d*d+x1*x1+y3*y3;
			delta=4*x1*x1-4*m;
			xx1=(-2*x1+sqrt(delta))/2;
			xx2=(-2*x1-sqrt(delta))/2;
			//cazul 2
			m=-2*yy2*y3-yy2*yy1-d*d+x1*x1+y3*y3;
			delta=4*x1*x1-4*m;
			xx3=(-2*x1+sqrt(delta))/2;
			xx4=(-2*x1-sqrt(delta))/2;
			
			//xx1 cu yy1
			nrtri+=bs(xx1,yy1,j+1,n-1);
			//xx2 cu yy1
			nrtri+=bs(xx2,yy1,j+1,n-1);
			//xx3 cu yy1
			nrtri+=bs(xx3,yy1,j+1,n-1);
			//xx4 cu yy1
			nrtri+=bs(xx4,yy1,j+1,n-1);
			//xx1 cu yy2
			nrtri+=bs(xx1,yy2,j+1,n-1);
			//xx2 cu yy2
			nrtri+=bs(xx2,yy2,j+1,n-1);
			//xx3 cu yy2
			nrtri+=bs(xx3,yy2,j+1,n-1);
			//xx4 cu yy2
			nrtri+=bs(xx4,yy2,j+1,n-1);
			
			printf("%.lf %.lf\n", xx1,yy1);
			printf("%.lf %.lf\n", xx2,yy1);
			printf("%.lf %.lf\n", xx3,yy1);
			printf("%.lf %.lf\n", xx4,yy1);
			printf("%.lf %.lf\n", xx1,yy2);
			printf("%.lf %.lf\n", xx2,yy2);
			printf("%.lf %.lf\n", xx3,yy2);
			printf("%.lf %.lf\n", xx4,yy2);*/
			
			//un triunghi e echilateral daca toate unghiurile au 60 grade
			q=M_PI/3.0;
			unghi=atan2(y2,x2);
			raza=sqrt(x2*x2+y2*y2);
			//sin 60 grade= rad(3)/2=0.9 aproximativ
			//q1=cos(unghi)*0.9+sin(unghi)*0.5;
			q1=cos(unghi-q);
			q2=sin(unghi-q);
			q3=cos(unghi+q);
			q4=sin(unghi+q);
			//cos 60 grade = 1/2=0.5
			//q2=cos(unghi)*0.5-sin(unghi)*0.9;
			//solutiile
			xx1=x1+raza*q1;
			yy1=y3+raza*q2;
			//printf("%.lf %lf\n", xx1,yy1);
			nrtri+=bs(xx1,yy1,j+1,n-1);
			xx1=x1+raza*q3;
			yy1=y3+raza*q4;
			nrtri+=bs(xx1,yy1,j+1,n-1);
			
			
		 }
		 
	printf("%d", nrtri);	 
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}