Cod sursa(job #8490)

Utilizator mockeBarca Cristian Mihai mocke Data 24 ianuarie 2007 21:08:45
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define NMAX 1024
#define EPS 1e-4

using namespace std;

typedef struct { float x, y; } per;

per P[NMAX], punct, punct1, punct2;

int i, j, N, M;
int Sol;	
int ok1, ok2;
float a, b;
float mx, my, dx, dy, x3, x4, y3, y4;
	
bool operator < (const per &A, const per &B)
{
	return ( A.x < B.x || ( fabs( A.x - B.x ) < EPS && A.y < B.y ));
}
	
inline int cmp_c(double x, double y)
{
    if (fabs(x-y) < EPS) return 0;
    if (x < y) return -1;
    return 1;
}

inline int cmp_p(per A, per B)
{
	  if (cmp_c(A.x, B.x) == 0 && cmp_c(A.y, B.y) == 0) return 0;
	  else 
	  if (cmp_c(A.x, B.x) == -1 || (cmp_c(A.x, B.x) == 0 && cmp_c(A.y, B.y) == -1)) return -1;
	  else 
	  if (cmp_c(A.x, B.x) == 1 || (cmp_c(A.x, B.x) == 0 && cmp_c(A.y, B.y) == 1)) return 1;   
	  
	  return 2;
}

int search(per X)
{
	int c, l = 1, r = N, temp;
	
	while (l <= r)
	{
		c = (l + r)/2;
		
		temp = cmp_p(P[c], X);
		
		if (temp == 0) return 1;
		else
		if (temp == 1) r = c-1;
		else
		if (temp == -1) 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;
}