Cod sursa(job #773342)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 1 august 2012 15:12:19
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 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.x<B.x)
		return 1;
	if (A.x==B.x)
		if (A.y<B.y)
			return 1;
	return 0;
}
void ec_dr(punct a, punct b, dre & ab)
{
	ab.a=b.y-a.y;
	ab.b=a.x-b.x;
	ab.c=a.x*a.y-a.x*b.y+a.y*b.x-a.y*a.x;
}

void ec2(double a, double b, double c,double &x1, double &x2)
{
	x1=(-b+sqrt(b*b-4*a*c))/(2*a);
	x2=(-b-sqrt(b*b-4*a*c))/(2*a);
}

double fabs( double x)
{
	if (x<0)
		return -x;
	return x;
}
double dist (punct a, punct b)
{
	return  sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
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
			if (a[mij].x<A.x)
				st=mij+1;
			else
				if (A.x>a[mij].y)
					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 rad=sqrt(3+0.0)/2,l1,m1,Dist,m2,l2,l3;
	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++)
		{
			l1=dist(a[i],a[j]);
			dre d;
			ec_dr(a[i],a[j],d);
			if (d.b!=0)
			{
				double A=(a[i].x+a[j].x)/2,B=(a[i].y-a[j].y)/2;
				double k=3/4*l1*l1,x,y,x1;
				m1=(-1*d.a/d.b);
				if (m1==0)
					m2=0;
				else
					m2=-1/m1;
				st=j+1;
				dr=n;
				dre d2;
				d2.a=m2;
				d2.b=-1;
				d2.c=B-m2*A;
				ec2(d2.b*d2.b+d2.a*d2.a,-2*A*d2.b*d2.b+2*d2.a*d2.c+B*d2.b*d2.a,A*A*d2.b*d2.b+d2.c*d2.c+B*d2.b*d2.c+B*B*d2.b*d2.b-k*d2.b*d2.b,x,x1);
				if (x>=a[j].x)
				{
					punct w;
					w.x=x;
					w.y=(-d2.c-d2.a*x)/d2.b;
					if (cauta(w))
					{
						sol++;
						break;
					}
				}
				else
					if (x1>=a[j].x)
					{
						x=x1;
						punct w;
						w.x=x;
						w.y=(-d2.c-d2.a*x)/d2.b;
						if (cauta(w))
						{
							sol++;
							break;
						}
					}
			}
		}
	g<<sol;
}