Cod sursa(job #324688)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 16 iunie 2009 21:30:06
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define Nmax 1510
#define eps 0.001
#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;

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);*/
			
		 }
		 
	printf("%d", nrtri);	 
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}