Cod sursa(job #492720)

Utilizator mgntMarius B mgnt Data 15 octombrie 2010 17:29:35
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;

double const EPS=0.001;
int const maxn=1500;
struct Pt{double x,y;} Z[maxn];int n;

bool eq(double u,double w)
{w-=u;if(0>w){w=-w;}return w<EPS;}

bool operator<(const Pt&A,const Pt&B)
{	bool b;
	if(eq(A.x,A.y)){b=A.y<B.y;}
	else{b=A.x<B.x;}
	return b;
}

bool bsrch(int k, double x,double y)
{	int a=k,b=n-1,m,q,u,w,r=-1;
	u=-1;
	while(a<=b)
	{	m=(a+b)/2;q=Z[m].x;
		if(eq(q,x)){u=m;b=m-1;}
		else{if(q<x){a=m+1;}else{b=m-1;}}
	}
	if(0<=u)
	{	w=-1;a=u;b=n-1;
		while(a<=b)
		{	m=(a+b)/2;q=Z[m].x;
			if(eq(q,x)){w=m;a=m+1;}else{b=m-1;}
		
		}
		while(u<=w)
		{	m=(a+b)/2;q=Z[m].y;
			if(eq(q,y)){r=y;u=w+1;}
			else{if(q<y){u=m+1;}else{w=m-1;}}
		}
	}
	return (-1!=r);
}

int main()
{	ifstream is("triang.in");
	ofstream os("triang.out");
	is>>n;int i,j,c=0;
	for(i=0;n>i;++i){is>>Z[i].x>>Z[i].y;}
	make_heap(&Z[0],&Z[n]);
	sort_heap(&Z[0],&Z[n]);
	const double a1=0.5, b1=sqrt(3.0)/2.0,
		a2=a1, b2=-b1;
	for(i=0;i<n;i++)
	{	for(j=i+1;j<n;j++)
		{	double x1=Z[i].x,y1=Z[i].y,
			x2=Z[j].x,y2=Z[j].y,dx=x2-x1,dy=y2-y1,
			x=x1+dx*a1-dy*b1,y=y1+dx*b1+dy*a1;
			int k=j+1;
			if(bsrch(k,x,y)){++c;}
			x=x1+dx*a2-dy*b2;y=y1+dx*b2+dy*a2;
			if(bsrch(k,x,y)){++c;}
		}
	}
	os<<c<<endl;
}