Cod sursa(job #501909)

Utilizator mihai995mihai995 mihai995 Data 16 noiembrie 2010 23:59:16
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
using namespace std;

struct punct{double x,y;} v[1<<11],P,Q;
int n,nr;

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

inline double dist(punct a,punct b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

inline void lat(punct a,punct b)
{
	P.y=Q.y=0.5*(a.y+b.y);
	double D=sqrt(0.75*dist(a,b));
	P.x=a.x-D;
	Q.x=a.x+D;
}

void setc(punct a,punct b)
{
	if (a.x==b.x)
	{
		lat(a,b);
		return;
	}
	double tg=(a.y-b.y)/(a.x-b.x),p=0.5*(a.x+b.x+a.y+b.y),A,B,C,D;
	punct d;
	d.x=0.5*(a.x+b.x);
	d.y=0.5*(a.y+b.y);
	A=tg*tg+1;
	B=-2*(p*tg+d.x*tg+d.y);
	C=p*p+d.x*d.x-2*p*d.x+d.y-0.75*dist(a,b);
	D=sqrt(B*B-4*A*C);
	P.y=(-B+D)/(2*A);
	Q.y=(-B-D)/(2*A);
	P.x=p-P.y*tg;
	Q.x=p-Q.y*tg;
}

bool cmp(punct a,punct b)
{
	return a.x<b.x || a.x==b.x && a.y<b.y;
}

inline bool ae(punct a,punct b)
{
	return abs(a.x-b.x)<0.001 && abs(a.y-b.y)<0.001;
}

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

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