Cod sursa(job #492832)

Utilizator mgntMarius B mgnt Data 16 octombrie 2010 00:35:14
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;

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

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

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

int bsrch(int k,double x,double y)
{	int a=k,b=n-1,m,t=-1;double q;
	while(a<=b)
	{	m=(a+b)/2;q=Z[m].x;
		if(eq(q,x)){t=m;b=m-1;}
		else{if(q<x){a=m+1;}else{b=m-1;}}
	}
	if(0<=t)
	{	a=t;b=a+L[a]-1;t=-1;
		while(a<=b)
		{	m=(a+b)/2;q=Z[m].y;
			if(eq(q,y)){t=m;a=b+1;}
			else{if(q<y){a=m+1;}else{b=m-1;}}
		}
	}
	return 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]);
	for(i=1,j=0;n>i;++i)
	{if(!eq(Z[i].x,Z[i].y)){L[j]=(i-j);j=i;}}
	L[j]=n-j;
	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=bsrch(j+1,x,y);
			if(-1!=k)
			{	++c;
				//os<<i<<' '<<j<<' '<<k<<endl;
			}
			x=x1+dx*a2-dy*b2;y=y1+dx*b2+dy*a2;
			k=bsrch(j+1,x,y);
			if(-1!=k)
			{	++c;
				//os<<i<<' '<<j<<' '<<k<<endl;
			}
		}
	}
	os<<c<<endl;
}