Cod sursa(job #21031)

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

using namespace std;


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

int n;
int npat;

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

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

bool bs( int a, int 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] >= 10 ) || ( absv(patr[ ind[i+step] ][0] - a ) <= 10 &&
				patr[ ind[i+step] ][1] - b < -10) )
				i += step;
		}
	if ( absv( patr[ ind[i+1] ][0] - a )<=10 && absv( patr[ ind[i+1] ][1] - b ) <= 10 ) return 1;
	
}

bool bs1( int a, int b )
{
	int i;
	for ( i = 1; i<= n; i++ )
		if ( absv(patr[i][0] - a)<=10 && absv(patr[i][1] - b ) <= 10 )
			return 1;
}

int main()
{
	int i,j;
	double a,b;

	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);

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

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

		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;
}