Cod sursa(job #8400)

Utilizator love_for_uSpancioc Riana love_for_u Data 24 ianuarie 2007 18:38:47
Problema Patrate 3 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <algorithm>
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define NMAX 1024
#define EPS 1e-4

using namespace std;

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

int i, j, N, M;
long long Sol;	
	
bool operator < (const per &A, const per &B)
{
	return ( A.x < B.x || ( ABS( A.x - B.x ) < EPS && A.y < B.y ));
}
	
inline int cmp (per A, per B)
{
	if (ABS( A.x - B.x ) < EPS && ABS( A.y - B.y ) < EPS ) return 2;
	
	return ( A.x < B.x || ( ABS( A.x - B.x ) < EPS && A.y < B.y ));
}

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

int exista(double x1, double y1, double x2, double y2)
{
	per punct;
   
	int ok1, ok2;
   
	x2 -= x1, y2 -= y1;

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

	punct.x = a + x1; punct.y = b + y1;
	 
	ok1 = search(1, N, punct);
	 
	punct.x = b + x1; punct.y = y1 - a;
	 
	ok2 = search(1, N, punct);
	 
	if (ok1 == ok2 && ok2 == 1) 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("%lf %lf", &P[i].x, &P[i].y);
	
	sort(P+1, P+N+1);
	
	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) ) Sol++;
		
	printf("%lld\n", Sol/2);
	
	return 0;
}