Cod sursa(job #409070)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 3 martie 2010 13:47:03
Problema Triang Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
using namespace std;
#include<fstream>
#include<cmath>
#include<algorithm>
#define sinus 0.8660254038
struct punct
{
	double x;
	double y;
};
int N,nr;
punct p[1505];
int comp(punct,punct);
void cauta(int,int,punct);
int main()
{
	int i,j,k;
	punct pp;
	double x1,y1,x2,y2,xx,yy,lat;
	ifstream fin("triang.in");
	fin>>N;
	for(i=1;i<=N;++i)
		fin>>p[i].x>>p[i].y;
	sort(p+1,p+N+1,comp);
	for(i=1;i<=N;++i)
	{
		x1=p[i].x;
		y1=p[i].y;
		for(j=1;j<=N;++j)
			if(j!=i)
			{
				x2=p[j].x;
				y2=p[j].y;
				xx=x2-x1;
				yy=y2-y1;
				pp.x=xx/2-sinus*yy+x1;
				pp.y=sinus*xx+yy/2+y1;
				cauta(1,N,pp);
			}
	}
	ofstream fout("triang.out");
	fout<<nr/2;
	return 0;
}
int comp(punct A,punct B)
{
	if(A.x<B.x)
		return 1;
	if(A.x==B.x)
	  if(A.y<B.y)
		return 1;
	return 0;
}
void cauta(int s,int d,punct pp)
{
    if(s<d)
    {
        int m=(s+d)/2;
        if(pp.x<p[m].x)
          if(p[m].x-pp.x>0.001)
            cauta(s,m-1,pp);
          else
            if(abs(p[m].y-pp.y)<=0.001)
              ++nr;
            else;
        else
          if(pp.x>p[m].x)
            if(pp.x-p[m].x>0.001)
              cauta(m+1,d,pp);
            else
              if(abs(p[m].y-pp.y)<=0.001)
                ++nr;
              else;
          else
            ++nr;
    }
}