Cod sursa(job #8482)

Utilizator mockeBarca Cristian Mihai mocke Data 24 ianuarie 2007 20:59:12
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 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;

typedef struct { double x, y; } per;

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

int i, j, N, M;
int Sol;	
int ok1, ok2;
double a, b;
double mx, my, dx, dy, x3, x4, y3, y4;
	
int cmp_c(double x, double y)
{
    if (fabs(x-y) < EPS) return 0;
    if (x < y) return -1;
    return +1;
}

int cmp(per A, per B)
{
    if (cmp_c(A.x, B.x) != 0) return (cmp_c(A.x, B.x) == -1);
    
	return (cmp_c(A.y, B.y) == -1);
}

int search(double px, double py)
{
    int l, r, c;
    
    l = 1, r = N;
	
    while (l <= r)
    {
          c = ((l + r) >> 1);
          if (cmp_c(P[c].x, px) == 0 && cmp_c(P[c].y, py) == 0) return 1;
          else 
		  if (cmp_c(P[c].x, px) == -1 || (cmp_c(P[c].x, px) == 0 && cmp_c(P[c].y, py) == -1)) l = c+1;
          else if (cmp_c(P[c].x, px) == +1 || (cmp_c(P[c].x, px) == 0 && cmp_c(P[c].y, py) == +1)) r = c-1;
    }
    
    return 0;
}

int exista(double x1, double y1, double x2, double 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;
	}*/
	
	mx = (x1 + x2) / 2, my = (y1 + y2) / 2;
	dx = fabs(mx - x1), dy = fabs(my - y1);
	
	if (y1 < y2)
	{
	     x3 = mx + dy, y3 = my - dx;
		 x4 = mx - dy, y4 = my + dx;
	}
	else
	{
	     x3 = mx - dy, y3 = my - dx;
		 x4 = mx + dy, y4 = my + dx;
    }
	
	ok1 = search(x3, y3);
	
	if (ok1)
	{
		ok2 = search(x4, y4);
		
		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("%lf %lf", &P[i].x, &P[i].y);
	
	sort(P+1, P+N+1, cmp);
	
	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;
}