Cod sursa(job #250)

Utilizator wefgefAndrei Grigorean wefgef Data 8 decembrie 2006 09:22:46
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define pi M_PI
#define egal(x, y) (fabs(x-y)<0.001)

#define Nmax 1505

pair<double, double> v[Nmax];
int n, rez;

void readdata()
{
	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%lf %lf", &v[i].x, &v[i].y);
}

int este(int st, int dr, double a, double b)
{
	int m;
	while (st != dr)
	{
		m = (st+dr)/2;
		if (egal(a, v[m].x) && egal(b, v[m].y)) return 1;
		if (v[m].x < a || (egal(v[m].x, a) && v[m].y < b)) st = m+1;
		else dr = m-1;
	}
	if (egal(a, v[st].x) && egal(b, v[st].y)) return 1;
	return 0;
}

void solve()
{
	double cos60, cos300, sin60, sin300, a, b;
	int i, j;
	
	sort(v, v+n);
	cos300 = cos60 = cos(pi/3);
	sin60 = sin(pi/3); sin300 = -sin60;
	
	for (i = 0; i < n-2; ++i)
	for (j = i+1; j < n-1; ++j)
	{
		
		a = v[i].x + (v[j].x-v[i].x)*cos60 - (v[j].y-v[i].y)*sin60;
		b = v[i].y + (v[j].x-v[i].x)*sin60 + (v[j].y-v[i].y)*cos60;
		if (a > v[j].x || (v[j].x == a && b > v[j].y))
			if (este(j+1, n, a, b)) ++rez;

		a = v[i].x + (v[j].x-v[i].x)*cos300 - (v[j].y-v[i].y)*sin300;
		b = v[i].y + (v[j].x-v[i].x)*sin300 + (v[j].y-v[i].y)*cos300;
		if (a > v[j].x || (v[j].x == a && b > v[j].y))
			if (este(j+1, n, a, b)) ++rez;
	}
	printf("%d\n", rez);
}

int main()
{
	readdata();
	solve();
	return 0;
}