Cod sursa(job #441950)

Utilizator bog29Antohi Bogdan bog29 Data 13 aprilie 2010 18:21:29
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream>
#include<math.h>
#define dmax 1503
#define erm 0.001
using namespace std;
ifstream in("triang.in");
ofstream out("triang.out");

int n,sol;
double x1,y11,x2,y2;

struct point
{	double x;
	double y;
}	p[dmax];

typedef int (*compfn)(const void *,const void *);

double dist(int i,int j)
{	return sqrt( (p[i].x - p[j].x)*(p[i].x - p[j].x) + ( p[i].y - p[j].y)*(p[i].y - p[j].y) );
}

int sf(struct point *a,struct point *b)
{	if(a->x != b->x)
	{	if(a->x > b->x)
			return 1;
		if(a->x < b->x)
			return -1;
		return 0;
	}	
	if(a->y > b->y)
			return 1;
		if(a->y < b->y)
			return -1;
		return 0;
}	

double absl(double k)
{	double s;
	s=k;
	if(k<0)
		s=(-1)*k;
	return s;
}

void bin_search(int i,int j,double xx,double yy)
{	int l,r,m;
	l=i+1;
	r=j-1;
	while(l<=r)
	{	m=(l+r)/2;
		if(absl(p[m].x - xx) <= erm)
		{	if(absl(p[m].y - yy) <=erm)
			{	sol++;
				//out<<i<<" "<<j<<" "<<m<<'\n';
				return;
			}
			else if(p[m].y < yy)
				while(p[m].y < yy)
				{	if(absl(p[m].y - yy) <=erm && absl(p[m].x - xx) <= erm)
					{	sol++;
						//out<<i<<" "<<j<<" "<<m<<'\n';
						return;	
					}
					m++;
				}	
			else if(p[m].y > yy)
				while(p[m].y > yy)
				{	if(absl(p[m].y - yy) <=erm && absl(p[m].x - xx) <= erm)
					{	sol++;
						//out<<i<<" "<<j<<" "<<m<<'\n';
						return;	
					}
					m--;
				}
			return;	
		}
		else if(p[m].x < xx && xx-p[m].x > erm)
			l=m+1;
		else if(p[m].x > xx && p[m].x - xx > erm)
			r=m-1;
	}	
}

void coord(int i,int j)
{	double dst,sn,cs,xmij,ymij,h;
	dst=dist(i,j);
	sn=absl(p[i].y - p[j].y) / dst;
	cs=(p[j].x - p[i].x) / dst;
	xmij=(p[i].x+p[j].x)/2;
	ymij=(p[i].y+p[j].y)/2;
	h=(dst/2)*sqrt(3);
	x1=xmij-h*sn; 
	y11=ymij+h*cs;
	x2=xmij+h*sn;
	y2=ymij-h*cs;
}	
	
int main()
{	int i,j;
	in>>n;
	for(i=0;i<n;i++)
		in>>p[i].x>>p[i].y;
	in.close();
	qsort( (void*)&p, n, sizeof(struct point), (compfn)sf );
	for(i=2;i<n;i++)
		for(j=0;j<i-1;j++)
		{	coord(j,i);
			bin_search(j,i,x1,y11);
			bin_search(j,i,x2,y2);
		}	
	out<<sol;	
	out.close();
	return 0;
}