Cod sursa(job #95363)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 28 octombrie 2007 14:05:35
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

#define fin  "triang.in"
#define fout "triang.out"

#define sz(c) (int)((c).size())
#define mp make_pair
#define pb push_back
#define x first
#define y second

#define EPS 0.0001

typedef pair <double,double> pct;
vector < pct > v;

int N,ret;

void readdata()
{
	int i;
	double a,b;

	freopen(fin,"r",stdin);

	scanf("%d",&N);

	for (i=0;i<N;++i)
	{
		scanf("%lf%lf",&a,&b);
		v.pb(mp(a,b));
	}
}

double dist(pct a,pct b)
{
	return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

double fabs(double a)
{
	if ( a < 0 ) a*=-1;
	return a;
}

int fsearch(pct M)
{
	int lo,hi,mid;

	lo=0; hi=sz(v)-1;

	while ( lo <= hi )
	{
		mid = ( lo + hi ) >> 1;
			
		if ( fabs( v[mid].x - M.x ) <= EPS ) 
		{
			if ( fabs( v[mid].y - M.y ) <= EPS )
				return 1;
			if ( v[mid].y < M.y )
				lo=mid+1;
			else
				hi=mid-1;
		}	
		else
			if ( v[mid].x < M.x )
				lo=mid+1;
			else
				hi=mid-1;
	}

	return 0;
}

void solve()
{
	int i,j;
	double a,b,c,t,m,n,f;
	pair <double,double> M1,M2;
	
	sort(v.begin(),v.end());

	for (i=0;i<sz(v);++i)
	for (j=i+1;j<sz(v);++j)
	{
		t = dist(v[i],v[j]);
		a = 2.0 * ( v[j].x - v[i].x );
		b = 2.0 * ( v[j].y - v[i].y );
		c = v[i].x*v[i].x + v[i].y*v[i].y - v[j].x*v[j].x - v[j].y*v[j].y;
		m = a*a + b*b;
		n = 2.0 * c * b + 2.0 * b * a * v[j].x;
		f = c*c + 2.0*c*a*v[j].x + a*a*(v[j].x*v[j].x + v[j].y*v[j].y) - a*a*t*t;

		M1.y = ( -n + sqrt( n*n-4*m*f ) ) / ( 2.0 * m );
		M2.y = ( -n - sqrt( n*n-4*m*f ) ) / ( 2.0 * m );
		M1.x = ( -c - b * M1.y ) / a;
		M2.x = ( -c - b * M2.y ) / a;

		ret += fsearch(M1);
		ret += fsearch(M2);

	}

	ret/=3;
	
	freopen(fout,"w",stdout);

	printf("%d\n",ret);
}

int main()
{
	readdata();
	solve();
	return 0;
}