Cod sursa(job #2890524)

Utilizator matthriscuMatt . matthriscu Data 15 aprilie 2022 20:33:11
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 1505

bool find(pair<double, double> p, pair<double, double> *v, int n)
{
	int i, step;
	for (step = 1; step <= n; step <<= 1);
	for (i = 1; step; step >>= 1)
		if (i + step <= n && p.first - v[i + step].first >= -1e-3 && p.second - v[i + step].second >= -1e-3)
			i += step;
	return abs(p.first - v[i].first) <= 1e-3 && abs(p.second - v[i].second) <= 1e-3;
}

int main()
{
	ifstream fin("triang.in");
	ofstream fout("triang.out");

	int n;
	fin >> n;

	pair<double, double> v[NMAX];
	
	for (int i = 1; i <= n; ++i)
		fin >> v[i].first >> v[i].second;
	
	sort(v + 1, v + n + 1);
	
	long long ans = 0;
	const double sqrt3 = sqrt(3);
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			pair<double, double> mid = {(v[i].first + v[j].first) / 2, (v[i].second + v[j].second) / 2};
			double slope = -1.0 * (v[j].second - v[i].second) / (v[j].first - v[i].first),
				   y_dist = (mid.first - v[i].first) * sqrt3, x_dist = y_dist * slope;

			ans += find({mid.first + x_dist, mid.second + y_dist}, v, n);
			ans += find({mid.first - x_dist, mid.second - y_dist}, v, n);
		}

	fout << ans / 3 << '\n';
}