Cod sursa(job #596311)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 16 iunie 2011 19:21:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
# include <fstream>
# include <algorithm>

# define eps 0.001
# define r3 1.732
using namespace std;


std :: ifstream f ("triang.in");
std :: ofstream g ("triang.out");

struct punct
{
	double x, y;
};

int n, i, j, sol;
punct v[1501];

inline double mod (double a)
{
	return a < 0 ? -a : a;
}

inline bool egal (double a, double b)
{
	return mod (a - b) < eps;
}

inline bool mic (double a, double b)
{
	return a - b <= 0;
}

inline punct p1 (punct a, punct b)
{
	punct c;
	c.x = (a.x - b.x - r3 * a.y - r3 * b.y) / 2;
	c.y = (a.y - b.y + r3 * a.x + r3 * b.x) / 2;
	return c;
}

inline punct p2 (punct a, punct b)
{
	punct c;
	c.x = (b.x - a.x - r3 * b.y - r3 * a.y) / 2;
	c.y = (b.y - a.y + r3 * b.x + r3 * a.x) / 2;
	return c;
}

inline int bs (punct c)
{
	int i, cnt = (1 << 11);
	for (i = 1; cnt > 0; cnt >>= 1)
	{
		int aux = i + cnt;
		if (aux <= n)
		{
			if (mic (v[aux].x, c.x) || (egal (v[aux].x, c.x) && mic (v[aux].y, c.y))) i = aux;
		}
	}
	
	return (egal (c.x, v[i].x) && egal (c.y, v[i].y) ? i : 0);
}

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

int main ()
{
	f >> n;
	for (i = 1; i <= n; ++i)
		f >> 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)
		{
			if ( bs (p1 (v[i], v[j])) ) ++sol;
			if ( bs (p2 (v[i], v[j])) ) ++sol;
		}
	
	g << sol << '\n';
	g.close ();
	return 0;
}