Cod sursa(job #1059783)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 16 decembrie 2013 22:32:22
Problema Patrate 3 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

#define MAXN 3005
int N, indSort[MAXN];
double coordX[MAXN], coordY[MAXN];

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

int SortComp(int a, int b)
{
	if (Compara(coordX[a], coordX[b]))
		return (coordY[a] < coordY[b]);
	return (coordX[a] < coordX[b]);
}

int CautaPunctul(int left, int right, double a, double b) //double
{
	if (left == right)
	{
		if (Compara(coordX[indSort[left]], a) && Compara(coordY[indSort[left]], b))
			return 1;
		else
			return 0;
	}

	int mijloc = (left + right) / 2;
	if (Compara(coordX[indSort[mijloc]], a) && Compara(coordY[indSort[mijloc]], b)) return 1;

	if (coordX[indSort[mijloc]] > a) CautaPunctul(left, mijloc, a, b);
	else if (coordX[indSort[mijloc]] < a) CautaPunctul(mijloc + 1, right, a, b);
	else if (coordY[indSort[mijloc]] >= b) CautaPunctul(left, mijloc, a, b);
	else CautaPunctul(mijloc + 1, right, a, b);
}

int main()
{
	int i, j, sol = 0;
	double x0, y0, x1, y1, mijX, mijY, dx, dy;

	f >> N;
	for (i = 1; i <= N; ++i)
		f >> coordX[i] >> coordY[i], indSort[i] = i;

	sort(indSort + 1, indSort + N + 1, SortComp);

	for (i = 1; i < N; ++i)
	for (j = i + 1; j <= N; ++j)
	{
		x0 = coordX[indSort[i]], y0 = coordY[indSort[i]];
		x1 = coordX[indSort[j]], y1 = coordY[indSort[j]];
		
		mijX = (x0 + x1) / 2, mijY = (y0 + y1) / 2;

		dx = mijX - x0, dy = mijY - y0;

		if ((CautaPunctul(1, N, mijX + dy, mijY - dx) && CautaPunctul(1, N, mijX - dy, mijY + dx)) ||
			(coordY[indSort[i]] == coordY[indSort[j]] && CautaPunctul(1, N, mijX + dy, mijY + dx) && CautaPunctul(1, N, mijX - dy, mijY - dx)))
		sol++;
	}

	g << sol/2 << '\n';

	return 0;
}