Cod sursa(job #615773)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 octombrie 2011 20:15:48
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 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;
const double eps = 0.001;
const double sin60 = (1.7320508) * 0.5, cos60 = 0.5;

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 C1;
			C1.x=p[i].x+(p[j].x-p[i].x)*cos60+(p[j].y-p[i].y)*sin60;
			C1.y=p[i].y-(p[j].x-p[i].x)*sin60+(p[j].y-p[i].y)*cos60;
			s_point C2;
			C2.x=p[i].x+(p[j].x-p[i].x)*cos60-(p[j].y-p[i].y)*sin60;
			C2.y=p[i].y+(p[j].x-p[i].x)*sin60+(p[j].y-p[i].y)*cos60;

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

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