Cod sursa(job #1288595)

Utilizator fhandreiAndrei Hareza fhandrei Data 8 decembrie 2014 22:06:16
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
// Include
#include <fstream>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
 
// Definitii
#define ll long long
#define point_t pair<int, int>
#define x first
#define y second
 
// Constante
const int sz = 1001;
const ll prec = 1000000LL;
 
// 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];
char current[15];

// Main
int main()
{
	in >> num;
	for(int i=1 ; i<=num ; ++i)
	{
		in >> current;
		int len = strlen(current);
		for(int j=0 ; j<len ; ++j)
		{
			if(current[j] != '.')
				points[i].x = points[i].x*10+current[j]-'0';
		}
		points[i].x *= 100;
		
		in >> current;
		len = strlen(current);
		for(int j=0 ; j<len ; ++j)
		{
			if(current[j] != '.')
				points[i].y = points[i].y*10+current[j]-'0';
		}
		points[i].y *= 100;
	}
	 
	sort(points+1, points+num+1);
	 
	for(int i=1 ; i<num ; ++i)
	{
		for(int j=i+1 ; j<=num ; ++j)
		{
			point_t point1, point2;
			point1.x = points[i].x + points[i].y - points[j].y;
			point1.y = points[i].y + points[j].x - points[i].x;
			
			point2.x = points[i].y + points[j].x - points[j].y;
            point2.y = points[j].x + points[j].y - points[i].x;
			
			if(binarySearch(point1) && binarySearch(point2))
				++squares;
		}
	}
	 
	out << (squares/2) << '\n';
	 
	in.close();
	out.close();
	return 0;
}
 
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 a.x/10==b.x/10 && a.y/10==b.y/10;
}