Cod sursa(job #513011)

Utilizator mihai995mihai995 mihai995 Data 14 decembrie 2010 22:17:35
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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,r3=1.732; 
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)
{
	if (A.x==B.x)
	{
		C1.x=A.x+r3*(A.y-B.y);
		C2.x=A.x+r3*(B.y-A.y);
		C1.y=C2.y=(A.y+B.y)/2;
		return;
	}
	long double tg,p,a,b,c,delta;
	tg=(A.y-B.y)/(A.x-B.x);
	p=(B.x*B.x+B.y*B.y-A.x*A.x-A.y*A.y)/(A.x-B.x);
	a=tg*tg+1;
	b=tg*p+2*A.x*tg-2*A.y;
	c=(p/2)*(p/2)+A.x*p-B.x*B.x-B.y*B.y+2*(A.x*B.x+A.y+B.y);
	delta=sqrt(b*b-4*a*c);
	C1.y=-(b+delta)/(2*a);
	C2.y=-(b-delta)/(2*a);
	C1.x=-(p/2+C1.y*tg);
	C2.x=-(p/2+C2.y*tg);
}

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<<"\n";
	return 0;
}