Cod sursa(job #655821)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 ianuarie 2012 15:10:49
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const char InFile[]="patrate3.in";
const char OutFile[]="patrate3.out";
const int MaxN=1024;
const double EPS=1e-4;

ifstream fin(InFile);
ofstream fout(OutFile);

inline double myabs(double x)
{
	if(x<0)
	{
		return -x;
	}
	return x;
}

inline bool equal(double x, double y)
{
	return myabs(x-y)<EPS;
}

struct Point
{
	Point(double x=0, double y=0):x(x),y(y){}

	bool operator< (const Point &a)
	{
		if(!equal(x,a.x))
		{
			return x<a.x;
		}
		return y<a.y;
	}

	bool operator== (const Point &a)
	{
		if(!equal(x,a.x))
		{
			return false;
		}
		if(!equal(y,a.y))
		{
			return false;
		}
		return true;
	}

	Point operator+ (const Point &a)
	{
		return Point(x+a.x,y+a.y);
	}

	Point operator* (const double &scalar)
	{
		return Point(x*scalar,y*scalar);
	}

	Point operator- (const Point &a)
	{
		return Point(x-a.x,y-a.y);
	}

	double magnitude()
	{
		return sqrt(x*x+y*y);
	}

	void normalize()
	{
		double d=magnitude();
		x/=d;
		y/=d;
	}

	void rotate90()
	{
		double aux=x;
		x=y;
		y=-aux;
	}

	double x,y;
};

struct Point_cmp
{
	inline bool operator() (const Point &a, const Point &b)
	{
		if(!equal(a.x,b.x))
		{
			return a.x<b.x;
		}
		return a.y<b.y;
	}
};

int N,sol;
Point V[MaxN];

inline bool mysearch(Point P)
{
	int p=1,u=N;
	while(p<=u)
	{
		int m=p+((u-p)>>1);
		if(P==V[m])
		{
			return true;
		}
		if(V[m]<P)
		{
			p=m+1;
		}
		else
		{
			u=m-1;
		}
	}
	return false;
}

inline double dist(const Point &a, const Point &b)
{
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>V[i].x>>V[i].y;
	}
	fin.close();

	sort(V+1,V+1+N,Point_cmp());

	for(register int i=1;i<=N;++i)
	{
		for(register int j=i+1;j<=N;++j)
		{
			double d=dist(V[i],V[j])*0.5;
			Point M=(V[i]+V[j])*0.5;
			Point N=V[j]-V[i];
			N.normalize();
			N=N*d;
			N.rotate90();
			Point P1=M+N,P2=M-N;

			if(mysearch(P1) && mysearch(P2))
			{
				++sol;
			}
		}
	}

	fout<<(sol>>1);
	fout.close();
	return 0;
}