Cod sursa(job #592416)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 28 mai 2011 12:20:49
Problema Triang Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 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,step,stp; float dst,v,rad;
float x,y,xm,ym,x11,y11,x22,y22,a,b,c;

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

inline bool equal ( float a, float 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,"%f %f",&A[i].x,&A[i].y);
	}
}

inline bool found( float x, float 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;
	}
	*/

    int i, step = stp;
    
	for ( i = 1; step; step >>= 1)
        if ( i + step <= n && (A[i + step].x < x || equal(A[i+step].x,x) ) )
           i += step;
	lim2 = i;
	
	step = stp;
	for ( i = 1 ; step; step >>= 1 )
		if ( i + step <= n && A[i+step].x < x )
			i += step;
	lim1 = i;
	
	for (step = 1; step < lim2 - lim1 + 1; step <<= 1);
	for ( i = lim1 ; step ; step >>= 1 )
		if ( i + step <= lim2 && (A[i+step].y < y || equal(A[i+step].y,y) ) )
			i += step;
	
	return equal(A[i].y,y); 
	
	
}

inline int solve () {
	
	sort( A+1,A+n+1,cmp() ); v = sqrt(3)/2;  for (stp = 1; stp < n; stp <<= 1);
	
	for ( i = 1 ; i < n ; ++i ){
		for ( j = i + 1 ; j <= n ; ++j ){
			dst = dist(A[i].x,A[i].y,A[j].x,A[j].y) * v;
			if ( equal(A[i].x,A[j].x) ){
				y = (A[i].y + A[j].y)/2;
				x = A[i].x + dst;
				
				if ( found(x,y) )
					++nrtri;
				
				x = A[i].x - dst;
				
				if ( found(x,y) )
					++nrtri;
				
				continue;
			}
			
			if ( equal(A[i].y,A[j].y) ){
				x = (A[i].x+A[j].x)/2; y = A[i].y + dst;
				if ( found(x,y) )
					++nrtri;
				y = A[i].y - dst;
				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;
			rad = sqrt((a*a*1.0)+(b*b*1.0));
			
			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;
			}
			
			x -= (2*a*dst*rad) / (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;
}