Cod sursa(job #622748)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 18 octombrie 2011 15:36:10
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define nmax 1510
#define eps 0.001
#define x first
#define y second

pair <double, double> v[nmax];
int n, sol;
double vr[nmax][nmax];

int search(double x, double y)
{
	int i, step;
	for (step=1; step<n; step<<=1);
	for (i=1; step>0; step>>=1)
		if (i+step<=n && v[i+step].x-x<=eps) i+=step;
	for (; i<=n; i++)
	{
		if (fabs(v[i].x-x)>eps) return 0;
		if (fabs(v[i].y-y)<=eps) return 1;	
	}
	return 0;
}

int main()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	scanf("%d", &n);
	int i, j;
	double m, x, y, medx, medy, lung, a, X, Y, ca, rad, cc;
	for (i=1; i<=n; i++) scanf("%lf %lf", &v[i].x, &v[i].y);
	sort (v+1, v+n+1);
	for (i=1; i<n; i++)
		for (j=i+1; j<=n; j++) 
		{
			x=v[j].x-v[i].x;
			y=v[j].y-v[i].y;
			lung=x*x+y*y;
			vr[i][j]=sqrt(3*lung/4);
		}
	for (i=1; i<n; i++)
		for (j=i+1; j<=n; j++)
		{
			x=v[j].x-v[i].x;
			y=v[j].y-v[i].y;
			lung=x*x+y*y;
			rad=vr[i][j];
			if (!y)
			{
				X=(v[i].x+v[j].x)/2;
				Y=v[i].y+rad;
			} else 
			if (!x)
			{
				X=v[i].x+rad;
				Y=(v[i].y+v[j].y)/2;
			} else
			{
				m=y/x;
				m=-1/m;
				medx=(v[j].x+v[i].x)/2;
				medy=(v[j].y+v[i].y)/2;
				a=3*lung/4/(m*m+1);
				a=sqrt(a);
				ca=a;
				X=a+medx;
				a=sqrt(3*lung/4-(X-medx)*(X-medx));
				cc=a;
				if (m>0) Y=a+medy; else Y=medy-a;
			}
			if (v[j].x-X<=eps || (fabs(v[j].x-X)<=eps && v[j].y-Y<=eps))	
				sol+=search(X, Y);
			if (!y)
			{
				X=(v[i].x+v[j].x)/2;
				Y=v[i].y-rad;
			} else 
			if (!x)
			{
				X=v[i].x-rad;
				Y=(v[i].y+v[j].y)/2;
			} else
			{
				X=-ca+medx;
				a=cc;
				if (m<0) Y=a+medy; else Y=medy-a;
			}
			if (v[j].x-X<=eps || (fabs(v[j].x-X)<=eps && v[j].y-Y<=eps))
				sol+=search(X, Y);
		}
	printf("%d\n",sol);
}