Cod sursa(job #805251)

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

int N;
my a[1515];

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

inline bool mic(int a, int b)
{
	if (a == b) return true;
	return a < b;
}

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 (egal(a[i + cnt].first, num.first) && mic(a[i + cnt].second, num.second))
			{
				i += cnt;
			}
			else
			if (mic(a[i + cnt].first, num.first))
			{
				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 int i = 1; i <= N; ++i)
	{
		pair<double, double> c;
		fin >> c.first >> c.second;
		a[i].first = c.first * 1000.0;
		a[i].second = c.second * 1000.0;
	}
	
	for (int i = 1; i <= N; ++i)
	{
		cout << a[i].first << ' ' << a[i].second << '\n';
	}
	cout << '\n';
	
	sort(a + 1, a + N + 1, cmp());
	
	int gg = 0;
	for (register int i = 1; i < N; ++i)
	{
		for (register 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 + 1.0 * sqrt(3.0) * sc;
			one.second = one.second - 1.0 * sqrt(3.0) * sl;
			
			two.first = two.first - 1.0 * sqrt(3.0) * sc;
			two.second = two.second + 1.0 * sqrt(3.0) * sl;
			
			cout << a[i].first << ' ' << a[i].second << '\n' << a[j].first << ' ' << a[j].second << '\n';
			cout << one.first << ' ' << one.second << '\n' << two.first << ' ' << two.second << '\n';
			cout << '\n';
			
			if (bs(one)) ++gg;
			if (bs(two)) ++gg;
		}
	}
	
	fout << gg / 3 << '\n';
	fout.close();
}