Cod sursa(job #410559)

Utilizator loginLogin Iustin Anca login Data 4 martie 2010 14:39:39
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
# include <fstream>
# include <iostream>
# define PI 3.14159265
# define EPS 0.0001
using namespace std;
struct pct {
	double x, y;
	friend bool operator < (const pct &a, const pct &b)
	{
		if(a.x+EPS<b.x || (a.x-b.x>-EPS && a.x-b.x<EPS  && a.y+EPS<b.y))
			return 1;
		return 0;
	}
};
pct v[1024];
int n, sol;

void read ()
{
	ifstream fin ("patrate3.in");
	fin>>n;
	for (int i=1;i<=n;i++)
		fin>>v[i].x>>v[i].y;
}

pct punct (pct a, pct b)
{
    pct p1;
	p1.x=cos(PI/2)*(b.x-a.x)-sin(PI/2)*(b.y-a.y)+a.x;
    p1.y=sin(PI/2)*(b.x-a.x)+cos(PI/2)*(b.y-a.y)+a.y;
    return p1;
}

int cauta (int st, int dr, pct a)
{
	if (st==dr)
	{
		if (v[st].x-a.x>-EPS && v[st].x-a.x<EPS && v[st].y-a.y>-EPS && v[st].y-a.y<EPS)
			return 1;
		return 0;
	}
	int m=(st+dr)/2;
	if (v[m].x-a.x>-EPS && v[m].x-a.x<EPS && v[m].y-a.y>-EPS && v[m].y-a.y<EPS)
		return 1;
	if (v[m]<a)
		return cauta (m+1, dr, a);
	return cauta (st, m, a);
}
void solve ()
{
	pct p1, p2, p;
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++)
		{
			p.x=(v[i].x+v[j].x)/2;
			p.y=(v[i].y+v[j].y)/2;
			p1=punct(p, v[i]);
			p2=punct(p, v[j]);
			if (cauta(1, n, p1))
				if (cauta(1, n, p2))
					sol++;
		}
}		
	
int main ()
{
	read();
	sort(v+1, v+n+1);
	solve ();
	ofstream fout ("patrate3.out");
	fout<<sol/2;
	return 0;
}