Cod sursa(job #848219)

Utilizator siminescuPaval Cristi Onisim siminescu Data 5 ianuarie 2013 00:22:42
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<fstream>
#include<cmath>
#include<algorithm>

using namespace std;

# define pi M_PI
# define maxN 1505

typedef struct point {
	double x, y;
};

int N;
point P[maxN];

void read()
{
	ifstream f("triang.in");
	
	f>> N;
	
	int i;
	for(i = 1; i <= N; ++i)
		f>> P[i].x >> P[i].y;
	
	f.close();
}

int equal(point a, point b)
{
	if(fabs(a.x - b.x) < 0.001 && fabs(a.y - b.y) < 0.001)
		return 1;
	return 0;
}

bool compare(point a, point b)
{
	if(fabs(a.x - b.x) < 0.001)
		return a.y < b.y;
	return a.x < b.x;
}

int exist(int l, int r, point p)
{
	int m;
	while(l < r)
	{
		m = (l + r) / 2;
		if(equal(P[m], p))
			return 1;
		if(P[m].x < p.x || (fabs(P[m].x - p.x) < 0.001 && P[m].y < p.y))
			l = m + 1;
		else
			r = m - 1;
	}
	if(equal(P[l], p))
		return 1;
	return 0;
}

void solve()
{
    double cos60, cos300, sin60, sin300;
	point p;
    int i, j, result = 0;
     
    cos300 = cos60 = cos(pi / 3);
    sin60 = sin(pi / 3); sin300 = -sin60;
     
    for (i = 1; i < N - 1; ++i)
		for (j = i + 1; j < N; ++j)
		{
         
			p.x = P[i].x + (P[j].x - P[i].x) * cos60 - (P[j].y - P[i].y) * sin60;
			p.y = P[i].y + (P[j].x - P[i].x) * sin60 + (P[j].y - P[i].y) * cos60;
			if (p.x > P[j].x || (P[j].x == p.x && p.y > P[j].y))
				if (exist(j + 1, N, p)) ++result;
 
			p.x = P[i].x + (P[j].x - P[i].x) * cos300 - (P[j].y - P[i].y) * sin300;
			p.y = P[i].y + (P[j].x - P[i].x) * sin300 + (P[j].y - P[i].y) * cos300;
			if (p.x > P[j].x || (P[j].x == p.x && p.y > P[j].y))
				if (exist(j + 1, N, p)) ++result;
		}
	
	ofstream g("triang.out");
    g<< result;
	g.close();
}

int main()
{
	read();
	sort(P + 1, P + N + 1, compare);
	solve();
	return 0;
}