Cod sursa(job #546725)

Utilizator tudorsTudor Siminic tudors Data 5 martie 2011 13:58:01
Problema Patrate 3 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,rez=0;
typedef struct {double x,y;} PUNCT;
PUNCT A[1001];

ifstream f("patrate3.in");
ofstream g("patrate3.out");

bool les (double a, double b)
{
	if (b-a>=0.0000001)
		return 1;
	return 0;
}

bool operator < (const PUNCT &a, const PUNCT &b)
{
	if (a.x<b.x)
		return 1;
	else if (a.x==b.x)
	{
		if (a.y<b.y)
			return 1;
	}
	return 0;
}

void citire()
{
	int i;
	f>>n;
	for (i=1;i<=n;++i)
		f>>A[i].x>>A[i].y;
	sort(A+1,A+n+1);
}

int comp(double a, double b)
{
	if (fabs(a-b)<0.0001)
		return 1;
	return 0;
}

int bs(PUNCT T)
{
	int st=1,dr=n,mij;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (comp(A[mij].x,T.x) && comp(A[mij].y,T.y))
			return 1;
		else  if (A[mij].x<T.x)
				st=mij+1;
		else if (A[mij].x>T.x)
			dr=mij-1;
		else if (A[mij].y<T.y)
			st=mij+1;
		else 
			dr=mij-1;
	}
	return 0;
}

void rezolva()
{
	int i,j;
	float mijx,mijy,dx,dy;
	PUNCT T,S;
	for (i=1;i<=n;++i)
		for (j=i+1;j<=n;++j)
		{
			mijx=(A[i].x+A[j].x)/2;
			mijy=(A[i].y+A[j].y)/2;
			dx=fabs(mijx-A[i].x);
			dy=fabs(mijy-A[i].y);
			if (A[i].y<A[j].y)
			{
				T.x=mijx+dy;
				T.y=mijy-dx;
				S.x=mijx-dy;
				S.y=mijy+dx;
			}
			else if (A[i].y>A[j].y)
			{
				T.x=mijx-dy;
				T.y=mijy-dx;
				S.x=mijx+dy;
				S.y=mijy+dx;
			}
			if (bs(T))
				if (bs(S))
					rez++;
		}
}

int main()
{	
	citire();
	rezolva();
	g<<(rez+1)/2;
	f.close();
	g.close();
	return 0;
}