Cod sursa(job #406914)

Utilizator cristiprgPrigoana Cristian cristiprg Data 1 martie 2010 21:29:58
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define DIM 1505
#define eps 1e-3

double mabs(double x)
{
	return x<0?-x:x;
}

struct point
{
	double x, y;
	point(){x=y=0;}
	point (double X, double Y){ x=X, y=Y;}
	friend bool operator < (point P1, point P2)
	{
		if(P1.x+eps>P2.x)
			return 0;
		if (P1.x +eps < P2.x)
			return 1;
		else
			if (mabs(P1.x - P2.x)<=eps)
				if (P1.y +eps< P2.y)
					return 1;
		return 0;

	}

	friend bool operator == (point A, point B)
	{
		if (mabs(A.x - B.x) <= eps && mabs(A.y - B.y) <= eps)
			return 1;
		return 0;
	}

} P[DIM];




int n, sol;

void read()
{
	FILE *f = fopen("triang.in", "r");
	fscanf(f, "%d", &n);
	for (int i = 1; i <= n; ++i)
		fscanf(f, "%lf%lf", &P[i].x, &P[i].y);
	fclose(f);
}

double dist(point A, point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) - (A.y - B.y) * (A.y - B.y));
}

bool caut(int st, int dr, point p)
{
	if (st > dr)
		return false;

	int m = (st + dr)>>1;
	if (P[m] == p)
		return true;

	if (P[m] < p)
		return caut(st, m-1, p);

	return caut(m+1, dr, p);

}


void solve()
{
	const double T = 3.1415 / 3;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
			if (i != j)
			{
			  //  printf ("%d %d\n", i, j);
				point p1, p2;
				p1.x = cos(T) * (P[i].x - P[j].x) - sin(T) * (P[i].y - P[j].y) + P[i].x;
				p1.y = sin(T) * (P[i].x - P[j].x) + cos(T) * (P[i].y - P[i].y) + P[i].y;

			//	printf ("p1 %lf %lf\n", p1.x, p1.y);

				p2.x = cos(T) * (P[j].x - P[i].x) - sin(T) * (P[j].y - P[i].y) + P[j].x;
				p2.y = sin(T) * (P[i].x - P[j].x) + cos(T) * (P[i].y - P[j].y) + P[j].y;

			//	printf ("p2 %lf %lf\n", p2.x, p2.y);

			//	sol += binary_search(P+1, P+n+1, p1);
			//	sol += binary_search(P+1, P+n+1, p2);

				sol += caut(i, j, p1);
				sol += caut(i,j,  p2);

			}
}

int main()
{
	read();
	sort(P+1, P+n+1);
//	cout<<caut(1,n,point(2.001,3.4644));
	solve();

	FILE *f = fopen("triang.out", "w");
	fprintf(f, "%d\n", sol);
	fclose(f);
	return 0;
}