Cod sursa(job #805266)

Utilizator VincentVegaVincent Vega VincentVega Data 31 octombrie 2012 01:05:58
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define S3 1.7320508075
#define my pair<long long, long long>
using namespace std;

long long N;
my a[1515];

struct cmp
{
	bool operator()(const my &a, const my &b)const
	{
		if (a.first == b.first)
		{
			return a.second < b.second;
		}
		return a.first < b.first;
	}
};

inline bool egal(int a, int b)
{
	int x = a - b;
	if (-100 <= x && x <= 100) return true;
	return false;
}

inline bool mic(my a, my b)
{
	if (egal(a.first, b.first))
	{
		if (egal(a.second, b.second))
		{
			return 1;
		}
		return a.second < b.second;
	}
	return a.first < b.first;
}

inline bool bs(my num)
{
	long long i = 0, cnt = 1 << 12;
	for (; cnt > 0; cnt >>= 1)
	{
		if (i + cnt <= N)
		{
			if (mic(a[i + cnt], num))
			{
				i += cnt;
			}
		}
	}
	
	if (egal(a[i].first, num.first) && egal(a[i].second, num.second)) return true;
	return false;
}

int main()
{
	ifstream fin("triang.in");
	ofstream fout("triang.out");
	
	fin >> N;
	for (register long long i = 1; i <= N; ++i)
	{
		pair<double, double> c;
		fin >> c.first >> c.second;
		a[i].first = c.first * 1000000;
		a[i].second = c.second * 1000000;
	}
	
	sort(a + 1, a + N + 1, cmp());
	
	
	//for (long long i = 1; i <= N; ++i)
	//{
	//	cout << a[i].first << ' ' << a[i].second << '\n';
	//}
	//cout << "\n\n\n\n";
	
	long long gg = 0;
	for (long long i = 1; i < N; ++i)
	{
		for (long long j = i + 1; j <= N; ++j)
		{
			my abc;
			long long sl, sc;
			abc.first = (a[i].first + a[j].first) / 2;
			abc.second = (a[i].second + a[j].second) / 2;
			
			sl = abc.first - a[j].first;
			sc = abc.second - a[j].second;
			
			my one, two;
			one = abc;
			two = abc;
			
			one.first = one.first + S3 * sc;
			one.second = one.second - S3 * sl;	
			two.first = two.first - S3 * sc;
			two.second = two.second + S3 * sl;
			
			//cout << "one " << one.first << ' ' << one.second << '\n';
			//cout << "two " << two.first << ' ' << two.second << '\n';
			
			if (bs(one)) ++gg;
			if (bs(two)) ++gg;
		}
	}
	
	fout << gg / 3 << '\n';
	fout.close();
}