Cod sursa(job #592110)

Utilizator ChallengeMurtaza Alexandru Challenge Data 26 mai 2011 19:40:01
Problema Triang Scor 0
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;
};

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

int N,sol;
s_point p[MaxN];

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

inline bool bs(s_point &a)
{
	int st=1,dr=N;
	while(st<=dr)
	{
		int m=st+((dr-st)>>1);
		if(d_equal(a.x,p[m].x))
		{
			if(d_equal(a.y,p[m].y))
			{
				return true;
			}
			else if(p[m].y<a.y)
			{
				dr=m-1;
			}
			else
			{
				st=m+1;
			}
		}
		else if(p[m].x<a.x)
		{
			dr=m-1;
		}
		else
		{
			st=m+1;
		}
	}
	return false;
}

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

			if(bs(C1))
			{
				++sol;
			}
			if(bs(C2))
			{
				++sol;
			}
		}
	}

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