Cod sursa(job #23381)

Utilizator damaDamaschin Mihai dama Data 28 februarie 2007 18:46:17
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#include <algorithm>
#define e 0.0001

using namespace std;

struct point
{
	double x, y;	
};

int n, cnt;
point v[1001];

bool cmp(point one, point two)
{
	return one.x < two.x || (one.x == two.x && one.y < two.y);
}
bool found(point);

int main()
{
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);
	
	int i, j;
	point c, u, t, f1, f2;
	
	scanf("%d", &n);
	
	for(i = 1; i <= n; ++i)
	{
		scanf("%lf%lf", &v[i].x, &v[i].y);
	}
	
	sort(v + 1, v + n + 1, cmp);
	
	for(i = 1; i < n; ++i)
	{
		for(j = i + 1; j <= n; ++j)
		{
			c.x = (v[i].x + v[j].x) / 2;
			c.y = (v[i].y + v[j].y) / 2;
			u.x = v[i].x - c.x;
			u.y = v[i].y - c.y;
			t.x = v[j].x - c.x;
			t.y = v[j].y - c.y;
			if(u.y <= 0)
			{
				f1.y = u.x + c.y;
				f1.x = -u.y + c.x;
				f2.y = t.x + c.y;
				f2.x = -t.y + c.x; 
			}
			else
			{
				f1.y = -u.x + c.y;
				f1.x = u.y + c.x;
				f2.y = -t.x + c.y;
				f2.x = t.y + c.x;
			} 
			
			if(found(f1) && found(f2))
			{
				++cnt;
			}
		}
	}
	
	cnt /= 2;
	printf("%d\n", cnt); 
	
	return 0;
}

bool found(point one)
{
	int min = 1, mid, max = n;
	
	while(min <= max)
	{
		mid = (min + max) / 2;
		if(one.x > v[mid].x + e)
		{
			min = mid + 1;
		}
		else if(one.x < v[mid].x - e)
		{
			max = mid - 1;
		} 
		else
		{
			if(one.y > v[mid].y + e)
			{
				min = mid + 1;
			}
			else if(one.y < v[mid].y - e)
			{
				max = mid - 1;
			}
			else
			{
				return 1;
			}
		}
	}
	return 0;
}