Cod sursa(job #8469)

Utilizator mockeBarca Cristian Mihai mocke Data 24 ianuarie 2007 20:18:54
Problema Patrate 3 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define NMAX 1024
#define EPS 1e-4

using namespace std;

struct per { float x, y; } P[NMAX], punct;

int i, j, N, M;
int Sol;	
int ok1, ok2;
float a, b;
	
bool operator < (const per &A, const per &B)
{
	return ( A.x < B.x || ( fabs( A.x - B.x ) < EPS && A.y < B.y ));
}
	
int cmp (per A, per B)
{
	if (fabs( A.x - B.x ) < EPS && fabs( A.y - B.y ) < EPS ) return 2;
	
	return ( A.x < B.x || ( fabs( A.x - B.x ) < EPS && A.y < B.y ));
}

int search(per X)
{
	int c, l = 1, r = N, temp;
	
	while (l <= r)
	{
		c = (l + r)/2;
		
		temp = cmp(X, P[c]);
		
		if (temp == 2) return 1;
		else
		if (temp == 1) r = c-1;
		else
		if (temp == 0) l = c+1;
	}
	
	return 0;
}

int exista(float x1, float y1, float x2, float y2)
{
	x2 -= x1, y2 -= y1;

	a = (x2-y2)/2.0, b = (x2+y2)/2.0;

	punct.x = a + x1; 
	punct.y = b + y1;  
	ok1 = search(punct);
	
	if (ok1)
	{		
		punct.x = b + x1; 
		punct.y = y1 - a;  
		ok2 = search(punct);
		
		if (ok2) return 1;
	}
	 
	return 0;
}


int main()
{
	
	freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);
	
	scanf("%d", &N);
	
	for (i = 1; i <= N; i++) scanf("%f %f", &P[i].x, &P[i].y);
	
	sort(P+1, P+N+1);
	
	Sol = 0;
	
	for (i = 1; i <= N; i++) 
		for (j = i + 1; j <= N; j++)
			if (exista(P[i].x, P[i].y, P[j].x, P[j].y)==1) Sol++;
		
	printf("%d\n", Sol/2);
	
	return 0;
}