Cod sursa(job #720216)

Utilizator danalex97Dan H Alexandru danalex97 Data 22 martie 2012 14:16:37
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
# include <fstream>
# include <algorithm>
# include<cmath>
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[1502];
double si,co=0.5,eps=0.001,r3;

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

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

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

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

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

int bs (int j, punct c)
{
	int i, cnt = (1 << 11);
	for (i = j + 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) ? 1 : 0);
}

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

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