Cod sursa(job #8423)

Utilizator love_for_uSpancioc Riana love_for_u Data 24 ianuarie 2007 19:21:37
Problema Patrate 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <algorithm>
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define NMAX 1024
#define EPS 1e-9

using namespace std;

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

int i, j, N, M;
int Sol;	
per punct1, punct2;
int ok1, ok2;
double dx, dy, mijx, mijy;
	
bool operator < (const per &A, const per &B)
{
	return ( A.x < B.x || ( ABS( A.x - B.x ) < EPS && A.y < B.y ));
}
	
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(per X)
{
	int c, l = 1, r = N, temp;
	
	while (l <= r)
	{
		c = (l + r)>>1;
		
		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)
{
	mijx = (x1 + x2)/2;
	mijy = (y1 + y2)/2;
	dx = ABS(mijx - x1);
	dy = ABS(mijy - y1);
	
	if (y1 < y2) 
	{ 
		  punct1.x = mijx + dy; 
		  punct1.y = mijy - dx; 
		  punct2.x = mijx - dy; 
		  punct2.y = mijy + dx; 
	}
	else 
	{
	      punct1.x = mijx - dy; 
	 	  punct1.y = mijy - dx; 
		  punct2.x = mijx + dy; 
		  punct2.y = mijy + dx; 
	}
	
	ok1 = search(punct1);
	ok2 = search(punct2);
	
	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);
	
	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) ) Sol++;
		
	printf("%d\n", Sol/2);
	
	return 0;
}