Cod sursa(job #744386)

Utilizator GrimpowRadu Andrei Grimpow Data 8 mai 2012 16:22:55
Problema Patrate 3 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<stdio.h>
#include<cmath>
#include<algorithm>

#define maxn 1005
#define eps 1e-4

using namespace std;

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

int n,i,j,sol;

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

struct _pct{
	double x;
	double y;
	
	friend bool operator < ( const _pct &a , const _pct &b ){
		if ( !equal(a.x,b.x) ){
			return a.x < b.x;
		}
		return a.y < b.y;
	}
}A[maxn],p11,p12,p21,p22;

	
struct cmp{
	inline bool operator () ( const _pct &a , const _pct &b ){
		if ( !equal(a.x,b.x) ){
			return a.x < b.x;
		}
		return a.y < b.y;
	}
};
	
inline double dist ( _pct a , _pct b ){
	double d = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
	d = sqrt(d);
	return d;
}

inline void find_points ( int ind , _pct &a , _pct &b ){
	double d = dist(A[i],A[j]); double m_init,m;
	
	if ( equal(A[i].x,A[j].x) ){
		a.x = A[i].x + d; b.x = A[i].x - d;
		a.y = b.y = A[ind].y;
		return ;
	}
	
	if ( equal(A[i].y,A[j].y) ){
		a.x = b.x = A[ind].x;
		a.y = A[i].y + d; b.y = A[i].y - d;
		return ;
	}
	
	m_init = (A[i].y-A[j].y) / (A[i].x-A[j].x);
	m = -1 / m_init;
	
	double Y = d / sqrt((m*m)+1);
	double X = m * Y;
	
	a.x = A[ind].x + Y;
	a.y = A[ind].y + X;
	b.x = A[ind].x - Y;
	b.y = A[ind].y - X;
}

inline bool find ( _pct X ){
	int p,m,u; p = 1; u = n;
	
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( equal(A[m].x,X.x) && equal(A[m].y,X.y) ){
			return 1;
		}
		if ( A[m] < X ){
			p = m + 1;
		}
		else{
			u = m - 1;
		}
	}
	
	return 0;
}

int main () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
	}
	
	sort(A+1,A+n+1,cmp());
	
	for ( i = 1 ; i < n ; ++i ){
		
		for ( j = i + 1 ; j <= n ; ++j ){
			
			find_points(i,p11,p12);
			find_points(j,p21,p22);
			
			if ( find(p11) && find(p21) ){
				++sol;
			}
			if ( find(p12) && find(p22) ){
				++sol;
			}
		}
	}
	
	fprintf(g,"%d\n",sol / 4);
	
	fclose(f);
	fclose(g);
	
	return 0;
}