Cod sursa(job #472960)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 27 iulie 2010 13:02:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <math.h>
#include <stdio.h>

#include <algorithm>

using namespace std;

#define eps 0.001

struct point
{
	double x, y;
};

int n;
point v[1502], pm, p1, p2;

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

inline double panta (point a, point b)
{
	if (fabs (a.y - b.y) < eps)
		return 1000000000;

	return (a.y - b.y) / (a.x - b.x);
}

inline int cmp (point a, point b)
{
	if (fabs (a.x - b.x) < eps)
		return a.y < b.y;
	return a.x < b.x;
}

int cautare (point p)
{
	int st = 1, dr = n, m, sol = 0;
	
	while (st <= dr)
	{
		m = (st + dr) >> 1;
		
		if (p.x - v[m].x >= eps || (fabs (p.x - v[m].x) < eps && p.y - v[m].y >= eps))
			st = m + 1;
		else
		{
			sol = m;
			dr = m - 1;
		}
	}
	
	return fabs (v[sol].x - p.x) < eps && fabs (v[sol].y - p.y) < eps;
}

int main ()
{
	freopen ("triang.in", "r", stdin);
	freopen ("triang.out", "w", stdout);
	
	scanf ("%d", &n);
	
	int i, j, sol = 0;
	double d, p, dx, dy;
	
	v[0].x = v[0].y = 2000000000;
	for (i = 1; i <= n; i ++)
		scanf ("%lf %lf", &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 ++)
		{
			pm.x = (v[i].x + v[j].x) * 0.5;
			pm.y = (v[i].y + v[j].y) * 0.5;
			
			d = dist (v[i], v[j]);
			p = panta (v[i], v[j]);
			
			dx = sqrt (0.75 * d * d / (1 + 1 / (p * p)));
			dy = dx / p;
			
			if (p < 0)
			{
				p1.x = pm.x + dx;
				p1.y = pm.y + dy;
				
				p2.x = pm.x - dx;
				p2.y = pm.y - dy;
			}
			else
			{
				p1.x = pm.x + dx;
				p1.y = pm.y - dy;
				
				p2.x = pm.x - dx;
				p2.y = pm.y + dy;
			}
			
			sol = sol + cautare (p1) + cautare (p2);
		}
	
	printf ("%d\n", sol);
	return 0;
}