Cod sursa(job #617488)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 octombrie 2011 22:28:00
Problema Triang Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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, r;
char u[nmax][nmax];

int search(int a, int b, double x, double y)
{
	int m, p=0, i;
	while (a<=b)
	{
		m=(a+b)/2;
		if (fabs(v[m].x-x)<=eps) 
		{
			p=m;
			b=m-1;
		} else
		if (v[m].x<x) a=m+1; else
			b=m-1;
	}
	if (!p) return 0;
	for (i=p; i<=n; i++)
	{
		if (fabs(v[i].y-y)<=eps) 
		{
			r=p;
			return 1;
		}
		if (fabs(v[i].x-x)>eps) return 0;
	}
	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;
	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++)
			if (!u[i][j])
		{
			x=v[j].x-v[i].x;
			y=v[j].y-v[i].y;
			lung=x*x+y*y;
			rad=sqrt(3*lung/4);
			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));
				if (m>0) Y=a+medy; else Y=medy-a;
			}
			r=-1;
			sol+=search(1, n, X, Y);
			if (r>-1)
			{
				u[i][j]=u[j][i]=u[i][r]=u[r][i]=u[j][r]=u[r][j]=1;
			}
			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=sqrt(3*lung/4-(X-medx)*(X-medx));
				if (m<0) Y=a+medy; else Y=medy-a;
			}
			r=-1;
			sol+=search(1, n, X, Y);
			if (r>-1)
			{
				u[i][j]=u[j][i]=u[i][r]=u[r][i]=u[j][r]=u[r][j]=1;
			}
		}
	printf("%d\n",sol);
}