Cod sursa(job #1113074)

Utilizator fhandreiAndrei Hareza fhandrei Data 20 februarie 2014 12:13:15
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
// Include
#include <fstream>
#include <utility>
#include <algorithm>
using namespace std;

// Definitii
#define point_t pair<double, double>
#define x first
#define y second

// Constante
const int sz = 1001;
const double err = 1e-3;

// Functii
point_t getPoint(point_t point, point_t mid);
bool binarySearch(point_t search);
bool eq(point_t a, point_t b);
template<class T> T ABS(T x);

// Variabile
ifstream in("patrate3.in");
ofstream out("patrate3.out");

int num;
int squares;

point_t points[sz];

// Main
int main()
{
	in >> num;
	for(int i=1 ; i<=num ; ++i)
		in >> points[i].x >> points[i].y;
	
	sort(points+1, points+num+1);
	
	for(int i=1 ; i<num ; ++i)
	{
		for(int j=i+1 ; j<=num ; ++j)
		{
			point_t mid;
			mid.x = (points[i].x + points[j].x)/2;
			mid.y = (points[i].y + points[j].y)/2;
			point_t point1 = getPoint(points[i], mid);
			point_t point2 = getPoint(points[j], mid);
			
			//out << point1.x << ' ' << point1.y << " | " << point2.x << ' ' << point2.y << '\n';
			
			if(binarySearch(point1) && binarySearch(point2))
			{
				++squares;
				//out << "AICI E BINE\n";
			}
		}
	}
	
	out << (squares/2) << '\n';
	
	in.close();
	out.close();
	return 0;
}

point_t getPoint(point_t point, point_t mid)
{
	point_t ans;
	ans.x = mid.x - point.y + mid.y;
	ans.y = mid.y + point.x - mid.x;
	
	return ans;
}

bool binarySearch(point_t search)
{
	int left=1, right=num;
	
	while(left<=right)
	{
		int mid = (left+right) / 2;
		
		if(eq(search, points[mid]))
			return true;
		
		if(search < points[mid])
			right = mid-1;
		else
			left = mid+1;
	}
	
	return false;
}

bool eq(point_t a, point_t b)
{
	return (ABS(a.x-b.x) < err) && (ABS(a.y-b.y) < err);	}

template<class T> T ABS(T x)
{	return x<0? -x : x;	}