Cod sursa(job #441819)

Utilizator bog29Antohi Bogdan bog29 Data 13 aprilie 2010 14:17:15
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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;

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;
}	

void bin_search(int i,int j)
{	int l,r,m;
	l=i;
	r=j;
	while(l<r)
	{	m=(l+r)/2;
		if( max(dist(i,m) - dist(j,m) , dist(j,m) - dist(i,m) ) <=erm )
		{	if( max(dist(i,j) - dist(j,m) , dist(j,m) - dist(i,j) ) <= erm)
				sol++;
			while(p[m+1].x == p[m].x)
			{	if( max(dist(i,j) - dist(j,m) , dist(j,m) - dist(i,j) ) <= erm)
				{	sol++;	
					return ;
				}
				m++;
			}	
			return;
		}
		else if(dist(i,m) < dist(j,m) )
			l=m+1;
		else if(dist(i,m) > dist(j,m) )
			r=m;
	}
}

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=1;i<n;i++)
		for(j=0;j<i;j++)
			bin_search(j,i);
	out<<sol;	
	out.close();
	return 0;
}