Cod sursa(job #596866)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 20 iunie 2011 09:12:12
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
# include <fstream>
# include <algorithm>
using namespace std;

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

struct punct { double x, y; } a[1001];

const double eps = 0.001;
const double si = 1.73205 / 2, co = 0.5;
int n, i, j, sol;

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

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

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

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);
}

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

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

inline int bs (punct p, int dr)
{
	int i, cnt = 1 << 10;
	for (i = 1; cnt > 0; cnt >>= 1)
		if (i + cnt <= dr)
			if (mic (a[i].x, p.x) || (egal (a[i].x, p.x) && mic (a[i].y, p.y))) i += cnt;
	return (egal (a[i].x, p.x) && egal (a[i].y, p.y));
}
int main ()
{
	f >> n;
	for (i = 1; i <= n; ++i)
		f >> a[i].x >> a[i].y;
	
	sort (a + 1, a + n + 1, cmp);
	
	for (i = 1; i < n; ++i)
		for (j = i + 1; j < n; ++j)
		{
			if (bs (p1 (a[i], a[j]), j + 1)) ++sol;
			if (bs (p2 (a[i], a[j]), j + 1)) ++sol;
		}
	
	g << sol << '\n';
	g.close ();
	return 0;
}