Cod sursa(job #615772)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 octombrie 2011 20:06:26
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const char InFile[]="triang.in";
const char OutFile[]="triang.out";
const int MaxN=2048;
const double EPS=1.0e-3;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_point
{
	double x,y;
};

int N,sol;
s_point p[MaxN];

inline bool d_equal(double a, double b)
{
	return fabs(a-b)<EPS;
}

struct cmp
{
	inline bool operator() (const s_point &a, const s_point &b)
	{
		if(!d_equal(a.x,b.x))
		{
			return a.x<b.x;
		}
		return a.y<b.y;
	}
};

inline bool d_lower(double a, double b)
{
	return a-b<EPS;
}

inline int bs(s_point &a, int st)
{
	for(int step=1<<11;step;step>>=1)
	{
		int index=st+step;
		if(index<=N)
		{
			if(d_lower(p[index].x,a.x) || (d_equal(p[index].x,a.x) && d_lower(p[index].y,a.y)))
			{
				st=index;
			}
		}
	}
	if(d_equal(a.x,p[st].x) && d_equal(a.y,p[st].y))
	{
		return 1;
	}
	return 0;
}

double dist(s_point a, s_point b)
{
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}

int main()
{
	double sqrt2over3=sqrt(3.0)*0.5;
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>p[i].x>>p[i].y;
	}
	fin.close();

	sort(p+1,p+1+N,cmp());
	for(register int i=1;i<N-1;++i)
	{
		for(register int j=i+1;j<N;++j)
		{
			s_point M;
			M.x=(p[i].x+p[j].x)*0.5;
			M.y=(p[i].y+p[j].y)*0.5;
			double dx=p[i].x-p[j].x;
			double dy=p[i].y-p[j].y;
			double d=sqrt(dx*dx+dy*dy);
			double oneoverd=1.0/d;
			s_point N;
			N.x=p[j].x-p[i].x;
			N.y=p[j].y-p[i].y;
			N.x*=oneoverd;
			N.y*=oneoverd;
			d*=sqrt2over3;

			s_point T=N;
			N.x=-T.y;
			N.y=T.x;

			s_point C1=M;
			C1.x+=N.x*d;
			C1.y+=N.y*d;

			d=-d;
			s_point C2=M;
			C2.x+=N.x*d;
			C2.y+=N.y*d;

			sol+=bs(C1,j+1);
			sol+=bs(C2,j+1);
		}
	}

	fout<<sol;
	fout.close();
	return 0;
}