Cod sursa(job #805242)

Utilizator VincentVegaVincent Vega VincentVega Data 31 octombrie 2012 00:01:16
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define my pair<int, int>
using namespace std;

int 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 bs(my num)
{
	int i = 0, cnt = 1 << 12;
	for (; cnt > 0; cnt >>= 1)
	{
		if (i + cnt <= N)
		{
			if (a[i + cnt].first == num.first && a[i + cnt].second <= num.second)
			{
				i += cnt;
			}
			else
			if (a[i + cnt].first < num.first)
			{
				i += cnt;
			}
		}
	}
	
	if (a[i].first == num.first && a[i].second == num.second) return true;
	return false;
}

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