Cod sursa(job #773536)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 1 august 2012 23:32:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<iostream>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;
const double Error=0.0001;
struct punct{double x,y;};
struct dre{double a,b,c;};
punct a[1600],M;
int n,sol;
int st,dr;
int cmp(punct A, punct B)
{
	if (A.y<B.y)
		return 1;
	if (A.y==B.y)
		if (A.x<B.x)
			return 1;
	return 0;
}
int cauta (punct A)
{
	while (st<=dr)
	{
		int mij;
		mij=(st+dr)/2;
		if (fabs(a[mij].x-A.x)<=Error)
			if (fabs(a[mij].y-A.y)<=Error)
				return 1;
			
		
		if (fabs(a[mij].x-A.x)<=Error)
			if (a[mij].y<A.y+Error)
				st=mij+1;
			else
				if (a[mij].y>A.y)
					dr=mij-1;
				else ;
		else
			if (a[mij].x<A.x)
				st=mij+1;
			else
				if (A.x<a[mij].x)
					dr=mij-1;
	}
	return 0;
}
int main(void)
{
	fstream f,g;
	f.open("triang.in",ios::in);
	g.open("triang.out",ios::out);
	f>>n;
	int i,j;
	double sin60=sqrt(3+0.0)/2, cos60=0.5;
	for (i=1;i<=n;i++)
		f>>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	for (i=1;i<=n-2;i++)
		for (j=i+1;j<=n-1;j++)
		{
			punct C;
			C.x= a[i].x+cos60*(a[j].x-a[i].x)+sin60*(a[i].y-a[j].y);
			C.y=a[i].y+sin60*(a[j].x-a[i].x)+cos60*(a[j].y-a[i].y);
			st=j+1;
			dr=n;
			if (cauta(C))
				sol++;
		}
	g<<sol;
}