Cod sursa(job #1048353)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 5 decembrie 2013 19:17:13
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <iomanip>
#include <cmath>
using namespace std;

#define NMAX 1001
#define ERROR 0.0001


struct point
{
	float x, y;
}p[NMAX];

int N;

float absN (float x)
{
	if ( x < 0 )
		return -x;
	else
		return x;
}

int compare ( point a, point b )
{
	if (absN (a.x - b.x) < ERROR)
		return a.y < b.y;
	return a.x < b.x;
}

int binSearch(int li, int ls, point val)
{
	int m = ( li + ls ) / 2;
	if ( absN (p[m].x - val.x) < ERROR && absN (p[m].y - val.y) < ERROR )
	{
		return 1;
	}
	else
	{
		if (li <= ls)
		{
			if ( compare(p[m], val) )
				binSearch (m + 1, ls, val);
			else
				binSearch (li, m-1, val);
				
		}
		else
			return -1;
	}
}

int main()
{

	FILE *f = fopen ("patrate3.in", "r");
	FILE *g = fopen ("patrate3.out", "w");

	fscanf (f, "%d", &N);
	for (int i = 0 ; i < N; i++)
	{
		fscanf (f, "%f %f", &p[i].x, &p[i].y);
	}

	//qsort (p, N, sizeof(point), compare);
	sort(p, p + N, compare); 


	for (int i = 0 ; i < N; i++)
	{
		fprintf(g, "%f %f\n", p[i].x, p[i].y); 
	}

	point A, B;
	int nrSquare = 0;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			float mijx = ( p[i].x + p[j].x ) / 2;
			float mijy = ( p[i].y + p[j].y ) / 2;
			float dx = absN ( mijx - p[i].x );
			float dy = absN ( mijy - p[i].y ); 
			if ( p[i].y < p[j].y )
			{
				A.x = mijx + dy;
				A.y = mijy - dx;
				B.x = mijx - dy;
				B.y = mijy + dx;
				
				if ( binSearch (0, N-1, A) > 0 && binSearch (0, N-1, B) > 0 )
					nrSquare++;
			}
			else
			{
				A.x = mijx - dy;
				A.y = mijy - dx;
				B.x = mijx + dy;
				B.y = mijy + dx;

				if ( binSearch (0, N-1, A) > 0 && binSearch (0, N-1, B) > 0 )
					nrSquare++;
			}
		}
	}
	fprintf(g, "%d", nrSquare / 2);
	fclose(f); fclose(g);
	return 0;
}