Cod sursa(job #406939)

Utilizator cristiprgPrigoana Cristian cristiprg Data 1 martie 2010 21:57:54
Problema Triang Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define DIM 1505
#define eps 1e-3
#define pb push_back

const double INF =  (1<<30);
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;
	}

};


vector<point> P;

int n, sol;

void read()
{

	FILE *f = fopen("triang.in", "r");
	fscanf(f, "%d", &n);
	point p;
	p.x = -INF, p.y = -INF;
	P.pb(p);
	for (int i = 1; i <= n; ++i)
		fscanf(f, "%lf%lf", &p.x, &p.y), P.pb(p);
	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.14159265 / 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 = P[j].x + (P[i].x - P[j].x) * cos(T) - (P[i].y - P[j].y) * sin(T);
				p1.y = P[j].x + (P[i].x - P[j].x) * sin(T) + (P[i].y - P[j].y) * cos(T);

		//		printf ("p1 %lf %lf\n", p1.x, p1.y);
                sol += binary_search(P.begin() + 1, P.end(), p1);//printf ("sol = %d\n", sol);
				p2.x = P[i].x + (P[j].x - P[i].x) * cos(T) - (P[j].y - P[i].y) * sin(T);
				p2.y = P[i].x + (P[j].x - P[i].x) * sin(T) + (P[j].y - P[i].y) * cos(T);

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


				sol += binary_search(P.begin() + 1, P.end(), p2);//printf ("sol = %d\n", sol);

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

			}
}

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

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