Cod sursa(job #482587)

Utilizator ooctavTuchila Octavian ooctav Data 3 septembrie 2010 21:50:37
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<cstdio>
#include<iostream>
#include<cmath>
#include<complex>
#define x first
#define y second
using namespace std;

const int NMAX = 3010;
const int lgNMAX = 11;
const int INF = 1000000;
pair<double, double> coord[NMAX];
int N;
double rad3 = sqrt((double)3);
long long SOL;

void citire()
{
	cin >> N;
	for(int i = 1 ; i <= N ; i++)
		cin >> coord[i].x >> coord[i].y;
	for(int i = N + 1 ; i < NMAX ; i++)
		coord[i].x = INF, coord[i].y = INF;
}

bool cautare_bin(pair<double, double> varf)
{
	pair<long long, long long> V, CR;
	int p = 1<<lgNMAX, rez = 0;
	V.x = (double)1000 * varf.x;
	V.y = (double)1000 * varf.y;
	while(p)
	{
		CR.x = (double)1000 * coord[rez + p].x;
		CR.y = (double)1000 * coord[rez + p].y;
		
		if(CR.x == 1000 * INF && CR.y == 1000 * INF);
		else if(V == CR)
			return 1;
		else if(V < CR)
			rez += p;
		p >>= 1;
	}
	return 0;
}

void rez()
{
	pair<double, double>varf;
	for(int i = 1 ; i < N ; i++)
		for(int j = i + 1 ; j <= N ; j++)
		{
			pair<double, double> n1, n2;
			n1.x = coord[i].x;n1.y = coord[i].y;
			n2.x = coord[j].x;n2.y = coord[j].y;
			
			varf.first = (n1.x/2 - (n1.y * rad3)/2) + (n2.x/2 + (n2.y * rad3)/2);
			varf.second = ((n1.x * rad3)/2 + n1.y/2) + (-(n2.x * rad3)/2 + n2.y/2);
			SOL += cautare_bin(varf);
			varf.first = (n1.x/2 + (n1.y * rad3)/2) + (n2.x/2 - (n2.y * rad3)/2);
			varf.second = (-(n1.x * rad3)/2 + n1.y/2) + ((n2.x * rad3)/2 + n2.y/2);
			SOL += cautare_bin(varf);
		}
}

int main()
{
	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);
	citire();
	sort(coord + 1, coord + N + 1);
	rez();
	printf("%lld\n", SOL);
	return 0;
}