Cod sursa(job #527260)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 30 ianuarie 2011 23:44:37
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define NMAX 1505
#define pdd pair <double,double>
#define a first
#define b second
#define PI 3.14159265
#define prec 0.0001
using namespace std;
int n,rez;
pdd A[NMAX],x,y;
double alfa;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&A[i].a,&A[i].b);
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
inline int egal(double x,double y)
{
	return modul(x-y)<prec;
}
void cbin(int start,pdd x)
{
	int j,i,step; 
	for (step=1; step<=n; step<<=1);
	for (i=start; step; step>>=1)
		if (i+step<=n && A[i+step].a<x.a)
			i+=step;
	i++;
	for (j=i; j<=n && egal(A[j].a,x.a); j++)
		if (egal(A[j].b,x.b))
			rez++;
}
void solve()
{
	int i,j;
	for (i=1; i<=n; i++)
	{
		for (j=i+1; j<=n; j++)
		{
			alfa=60*PI/180;
			x.a=A[i].a+(A[j].a-A[i].a)*cos(alfa)-(A[j].b-A[i].b)*sin(alfa);
			x.b=A[i].b+(A[j].a-A[i].a)*sin(alfa)+(A[j].b-A[i].b)*cos(alfa);
			cbin(j,x);
			alfa=300*PI/180;
			y.a=A[i].a+(A[j].a-A[i].a)*cos(alfa)-(A[j].b-A[i].b)*sin(alfa);
			y.b=A[i].b+(A[j].a-A[i].a)*sin(alfa)+(A[j].b-A[i].b)*cos(alfa);
			cbin(j,y);
		}
	}
}
int main()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	read();
	sort(A+1,A+n+1);
	solve();
	printf("%d\n",rez);
	return 0;
}