Cod sursa(job #592394)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 28 mai 2011 11:33:01
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>

#define maxN 1505
#define eps 1e-3

using namespace std;

FILE*f=fopen("triang.in","r");
FILE*g=fopen("triang.out","w");

int nrtri,i,j,n; 
double x,y,xm,ym,x11,y11,x22,y22,a,b,c;

struct pct{
	double x;
	double y;
}A[maxN];
	
double dist(double x11,double y11,double x22,double y22 ){
	double aux = (x11-x22)*(x11-x22) + (y11-y22)*(y11-y22);
	return sqrt(aux);
}

inline bool equal ( double a, double b ){
	if ( fabs(a-b) < eps )
		return 1;
	return 0;
}

struct cmp{
	inline bool operator () ( const pct &a, const pct &b ) {
		if ( equal(a.x,b.x) )
			return a.y < b.y;
		return a.x < b.x;
	}
};

inline void citire() {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
	}
}

inline bool found( double x, double y ){
	int p,m,u,lim1,lim2;
	p = 1 ; u = n;
	
	while ( p <= u ){
		m = (p + u)>>1;
		
		if ( A[m].x > x || equal(x,A[m].x) )
			u = m - 1;
		else
			p = m + 1;
	}
	lim1 = p;
	
	p = 1 ; u = n;
	
	while ( p <= u ){
		m = (p + u)>>1;
		
		if ( A[m].x < x || equal(x,A[m].x) )
			p = m + 1;
		else
			u = m - 1;
	}
	lim2 = u;
	
	p = lim1; u = lim2;
	
	while ( p <= u ){
		m = (p + u)>>1;
		if ( equal(A[m].y,y) )
			return 1;
		if ( A[m].y > y )
			u = m - 1;
		else
			p = m + 1;
	}
	
	return 0;
}

inline int solve () {
	
	sort( A+1,A+n+1,cmp() );
	
	for ( i = 1 ; i < n ; ++i ){
		for ( j = i + 1 ; j <= n ; ++j ){
			if ( equal(A[i].x,A[j].x) ){
				y = (A[i].y + A[j].y)/2;
				x = A[i].x + dist(A[i].x,A[i].y,A[j].x,A[j].y) * sqrt(3)/2;
				
				if ( found(x,y) )
					++nrtri;
				
				x = A[i].x - dist(A[i].x,A[i].y,A[j].x,A[j].y) * sqrt(3)/2;
				
				if ( found(x,y) )
					++nrtri;
				
				continue;
			}
			
			if ( equal(A[i].y,A[j].y) ){
				//x = (A[i].x + A[j].x)/2 + dist(A[i].x,A[i].y,A[j].x,A[j].y) * sqrt(3)/2;
				x = (A[i].x+A[j].x)/2; y = A[i].y + dist(A[i].x,A[i].y,A[j].x,A[j].y) * sqrt(3)/2;
				if ( found(x,y) )
					++nrtri;
				y = A[i].y - dist(A[i].x,A[i].y,A[j].x,A[j].y) * sqrt(3)/2;
				if ( found(x,y) )
					++nrtri;
				
				continue;
			}
			
			x11 = A[i].x; y11 = A[i].y; x22 = A[j].x; y22 = A[j].y;
			xm = (x11+x22)/2; ym = (y11+y22)/2; a = y22-y11; b = x11-x22; c = y11*x22 - x11 * y22;
			double rad = sqrt((a*a*1.0)+(b*b*1.0)); double dst = dist(x11,y11,x22,y22) * sqrt(3) / 2;
			
			x = a*dst*rad - a*c - a*b*ym + b*b*xm; x /= (a*a+b*b);
			y = (b / a); 
			y *= ( x - xm ) ;
			y += ym;
			
			if ( found(x,y) ){
				++nrtri;
			}
			
			x = -a*dst*rad - a*c - a*b*ym + b*b*xm; x /= (a*a+b*b);
			y = (b / a) * ( x - xm ) + ym;
			
			if ( found(x,y) ){
				++nrtri;
			}
		}
	}
	
	nrtri /= 3;
	return nrtri;
}

int main () {
	
	citire();

	fprintf( g,"%d\n",solve() );
	
	fclose(f);
	fclose(g);
	
	return 0;
}