Cod sursa(job #21048)

Utilizator webspiderDumitru Bogdan webspider Data 22 februarie 2007 20:52:52
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

const double ESP = 10e-4;

double patr[1001][2];
double x1,y1,x2,y2;
int ind[1001];

int n;
int npat;

double absv( double x )
{
	if ( x < 0 ) return (-1)*x;
	return x;
}
	

bool cmpf( const int &a, const int &b )
{
	if (patr[a][0] - patr[b][0] > ESP) return 0;
	if (patr[a][0] - patr[b][0] < ESP) return 1;
	if (patr[a][1] - patr[b][1] > ESP) return 0;
	if (patr[a][1] - patr[b][1] < ESP) return 1;
	return 1;
}

bool bs( double a, double b )
{
	int step;
	int i=0;
	for ( step = 1; step <= n; step <<= 1 );
	for (; step; step >>= 1 )
		if ( i + step <= n )
		{
			if ( ( a - patr[ ind[i+step] ][0] > ESP ) || ( absv(patr[ ind[i+step] ][0] - a ) <= ESP &&
						patr[ ind[i+step] ][1] - b < -1*ESP ) )
				i += step;
		}
	if ( absv( patr[ ind[i+1] ][0] - a )<= ESP && absv( patr[ ind[i+1] ][1] - b ) <= ESP ) return 1;
	return 0;
}

int main()
{
	int i,j;
	
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);

	scanf("%d\n", &n);

	for ( i = 1; i <= n; i++ )
	{
		scanf("%lf %lf\n", &patr[i][0], &patr[i][1] );

		ind[ i ] = i;
	}

	sort( ind+1, ind+n+1, cmpf );

	for ( i = 1; i <= n; i++ )
		for ( j = i+1; j <= n; j++ )
	{
		// FIRST 
		x1 = patr[ ind[i] ][0] - ( patr[ ind[j] ][1] - patr[ ind[i] ][1] );
		y1 = patr[ ind[i] ][1] - ( patr[ ind[i] ][0] - patr[ ind[j] ][0] );

		x2 = patr[ ind[j] ][0] - ( patr[ ind[j] ][1] - patr[ ind[i] ][1] );
		y2 = patr[ ind[j] ][1] - ( patr[ ind[i] ][0] - patr[ ind[j] ][0] );

		if ( bs( x1,y1 ) && bs( x2, y2 ) )
			npat++;
	}

	printf("%d\n", npat/2);

	fclose(stdin);
	fclose(stdout);

	return 0;
}