Cod sursa(job #1348356)

Utilizator BLz0rDospra Cristian BLz0r Data 19 februarie 2015 17:35:39
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define Nmax 1502
#define eps 1.0 / 1e4
#define rad3p2 0.8660254037

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

struct point{
	double x, y;
}v[Nmax];
	
int N;

inline double sqr ( double x ){
	return x * x;
}
	
double getDist ( point a, point b ){
	return sqrt ( sqr ( a.x - b.x ) + sqr ( a.y - b.y ) );
}

bool cmp ( point a, point b ){
	
	if ( fabs ( a.x - b.x ) <= eps )
		return a.y < b.y;
	
	return a.x < b.x;
}

bool match ( point a, point b ){
	if ( fabs ( a.x - b.x ) <= eps && fabs ( a.y - b.y ) <= eps )
		return 1;
	return 0;
}

bool bSearch ( point T, int x ){
	int st = x + 1, dr = N, mid;
	
	while ( st <= dr ){
		mid = ( st + dr ) >> 1;
		
		if ( match ( T, v[mid] ) )
			return 1;
		
		if ( cmp ( v[mid], T ) )
			st = mid + 1;
		else
			dr = mid - 1;
		
	}
	return 0;
}

int main (){
	int sol = 0;
	point aux;
	
	fscanf ( f, "%d", &N );
	
	for ( int i = 1; i <= N; ++i )
		fscanf ( f,"%lf%lf", &v[i].x, &v[i].y );
	
	sort ( v + 1, v + N +1, cmp );
	
	for ( int i = 1; i < N; ++i ){
		for ( int j = i + 1; j <= N; ++j ){
			
			aux.x = ( v[i].x + v[j].x ) / 2 + rad3p2 * ( v[i].y - v[j].y );
			aux.y = ( v[i].y + v[j].y ) / 2 + rad3p2 * ( v[j].x - v[i].x );
			if ( bSearch ( aux, j ) ) 
				sol++;
			
			aux.x = ( v[i].x + v[j].x ) / 2 + rad3p2 * ( v[j].y - v[i].y );
			aux.y = ( v[i].y + v[j].y ) / 2 + rad3p2 * ( v[i].x - v[j].x );
			if ( bSearch ( aux, j ) )
				sol++;
		}
	}
	
	fprintf ( g, "%d", sol );
	
	return 0;	
}