Cod sursa(job #492771)

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

double const EPS=0.0001;
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,B.x)){if(eq(A.y,B.y)){b=false;}else{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,t=-1;Pt q={x,y};
	while(a<=b)
	{	m=(a+b)/2;
		if(q<Z[m]){a=m+1;}else{if(Z[m]<q){b=m-1;}else{t=m;a=b+1;}}
	}
	return 0<=t;
}

int main()
{	ifstream is("triang.in");
	ofstream os("triang.out");
	is>>n;int i,j,c=0,k;
	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+2<n;i++)
	{	for(j=i+1;j+1<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;
			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;
}