Cod sursa(job #516909)

Utilizator mihai995mihai995 mihai995 Data 26 decembrie 2010 23:12:42
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <cmath>
using namespace std;

struct punct{long double x,y;} v[1<<11],C1,C2;
const long double E=0.001;
long double r3;
int n;

ifstream in("triang.in");
ofstream out("triang.out");

inline bool egal(punct A,punct B)
{
	return abs(B.x-A.x)<E && abs(B.y-A.y)<E;
}

inline bool mai_mic(punct A,punct B)
{
	return B.x-A.x>E || abs(B.x-A.x)<E && B.y-A.y>E;
}

inline bool ok(punct A,punct B)
{
	return mai_mic(A,B) || egal(A,B);
}

void settle(punct A,punct B)
{
	punct D;
	long double L,tg,sin,cos;
	D.x=(A.x+B.x)/2;
	D.y=(A.y+B.y)/2;
	L=sqrt(((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y))*3)/2;
	if (A.x==B.x)
	{
		C1.x=D.x+L;
		C2.x=D.x-L;
		C1.y=C2.y=D.y;
		return;
	}
	if (A.y==B.y)
	{
		C1.y=D.y+L;
		C2.y=D.y-L;
		C1.x=C2.x=D.x;
		return;
	}
	tg=-(A.x-B.x)/(A.y-B.y);
	sin=abs(tg)/sqrt(tg*tg+1);
	cos=1/sqrt(tg*tg+1);
	if (tg<0)
		cos=-cos;
	C1.x=D.x+cos*L;
	C2.x=D.x-cos*L;
	C1.y=D.y+sin*L;
	C2.y=D.y-sin*L;
}

bool bs(int i,punct x)
{
	for (int step=1<<10;step;step>>=1)
		if (i+step<=n && ok(v[i+step],x))
			i+=step;
	return egal(v[i],x);
}

int main()
{
	int i,j,nr=0;
	in>>n;
	for (i=1;i<=n;i++)
		in>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,mai_mic);
	for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++)
		{
			settle(v[i],v[j]);
			nr+=bs(0,C1);
			nr+=bs(0,C2);
		}
	out<<nr/3<<"\n";
	return 0;
}