Cod sursa(job #805182)

Utilizator VincentVegaVincent Vega VincentVega Data 30 octombrie 2012 22:46:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define DBG 0
#define mytype pair<float, float>
using namespace std;

int N, sol;
mytype a[1515];

inline bool smaller(double a, double b)
{
	if (b - a >= 0.01) return true;
	return false;
}

inline bool equal(double a, double b)
{
	double var = a - b;
	if (var < 0) var = -var;
	
	if (var <= 0.01) return true;
	return false;
}

struct cmp
{
	inline bool operator()(const mytype &a, const mytype &b)
	{
		if (equal(a.first, b.first))
		{
			return smaller(a.second, b.second);
		}
		return smaller(a.first, b.first);
	}
};


inline bool bs(mytype var)
{
	int i = 0, cnt = 1 << 11;
	for (; cnt > 0; cnt >>= 1)
	{
		if (i + cnt <= N)
		{
			if (equal(a[i + cnt].first, var.first) && (smaller(a[i + cnt].second, var.second)))
			{
				i += cnt;
			}
			else
			if(smaller(a[i + cnt].first, var.first))
			{
				i += cnt;
			}
		}
	}
	
	if (equal(a[i].first, var.first) && equal(a[i].second, var.second)) return true;
	return false;
}

inline void DEBUG(string name, mytype a)
{
	if (DBG)
	{
		cout << name << ' ';
		cout << a.first << ' ' << a.second << '\n';
	}
}

int main()
{
	ifstream fin("triang.in");
	ofstream fout("triang.out");
	
	fin >> N;
	for (int i = 1; i <= N; ++i)
	{
		fin >> a[i].first >> a[i].second;
	}
	
	sort(a + 1, a + N + 1, cmp());
	
	for (int i = 1; i < N; ++i)
	{
		for (int j = i + 1; j <= N; ++j)
		{
			double sl, sc;
			mytype abc;
			abc.first = (a[i].first + a[j].first) / 2.0;
			abc.second = (a[i].second + a[j].second) / 2.0;
			
			sl = abc.first - a[j].first;
			sc = abc.second - a[j].second;
			
			mytype one, two;
			one = abc;
			two = abc;
			
			one.first = one.first + sqrt(3.0) * sc;
			one.second = one.second - sqrt(3.0) * sl;
			
			two.first = two.first - sqrt(3.0) * sc;
			two.second = two.second + sqrt(3.0) * sl;
			
			if (bs(one)) ++sol;
			if (bs(two)) ++sol;
			
			DEBUG("a[i]", a[i]);
			DEBUG("a[j]", a[j]);
			DEBUG("abc", abc);
			DEBUG("one", one);
			DEBUG("two", two);
			cout << '\n';
		}
	}
	
	fout << sol  << '\n';
	fout.close();
	return 0;
}