Cod sursa(job #596797)

Utilizator cont_de_testeCont Teste cont_de_teste Data 19 iunie 2011 22:26:24
Problema Triang Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <math.h>

#include <vector>
#include <algorithm>

using namespace std;

#define eps 1e-6

vector<pair<double, double> > v;
int i, j, k, N, ntri;
double a, b, xa, ya, xb, yb, u, R, xc, yc, pi;

int mai_mic(double a, double b)
{
	if (a < b && fabs(b - a) > eps)
		return 1;

	return 0;
}

int mai_mare(double a, double b)
{
	if (a > b && fabs(b - a) > eps)
		return 1;

	return 0;
}


int find(double x, double y, int li, int ls)
{
	int m;

	while (li <= ls)
	{
		m = (li + ls) >> 1;

		if (mai_mic(v[m].first, x))
			li = m + 1;
		else
		if (mai_mare(v[m].first, x))
			ls = m - 1;
		else
		if (mai_mic(v[m].second, y))
			li = m + 1;
		else
		if (mai_mare(v[m].second, y))
			ls = m - 1;
		else
			return 1;
	}

	return 0;
}

int main()
{
	pi = 2.0 * acos(0);

	freopen("triang.in", "r", stdin);

	scanf("%d", &N);
v.resize (N+1);

	for (i = 0; i < N; i++)
	{
		scanf("%lf %lf", &v[i].first, &v[i].second);
		//v.push_back(make_pair(a, b));
	}

	sort(v.begin(), v.end());

	ntri = 0;

	for (i = 0; i < N; i++)
		for (j = i + 1; j < N; j++)
		{
			xa = v[i].first, ya = v[i].second;
			xb = v[j].first, yb = v[j].second;

			xb -= xa;
			yb -= ya;
			u = atan2(yb, xb);
			R = sqrt(xb * xb + yb * yb);

			xc = xa + R * cos(u + pi / 3.0);
			yc = ya + R * sin(u + pi / 3.0);

			ntri += find(xc, yc, j + 1, N - 1);

			xc = xa + R * cos(u - pi / 3.0);
			yc = ya + R * sin(u - pi / 3.0);

			ntri += find(xc, yc, j + 1, N - 1);
		}

	freopen("triang.out", "w", stdout);
	printf("%d\n", ntri);

	return 0;
}