Cod sursa(job #2891099)

Utilizator matthriscuMatt . matthriscu Data 17 aprilie 2022 15:40:35
Problema Triang Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

#define eps 1e-5
#define NMAX 1505
typedef long double ld;

long double dist_sq(const pair<ld, ld> &a, const pair<ld, ld> &b)
{
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

long double slope(const pair<ld, ld> &a, const pair<ld, ld> &b)
{
	return (a.second - b.second) / (a.first - b.first);
}

bool find(const pair<ld, ld> &p, pair<ld, ld> *v, const int &n)
{
	int st = 1, dr = n;
	while (st <= dr) {
		int mid = (st + dr) / 2;
		if (abs(p.first - v[mid].first) < eps && abs(p.second - v[mid].second) < eps)
			return 1;
		else if (p < v[mid])
			dr = mid - 1;
		else
			st = mid + 1;
	}
	return 0;
}

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

	int n;
	fin >> n;

	pair<ld, ld> 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;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			ld m = -slope(v[i], v[j]),
			   beta = sqrt(0.75 * dist_sq(v[i], v[j]) / (m * m + 1)),
			   alpha = m * beta;

			pair<ld, ld> mid = {(v[i].first + v[j].first) / 2, (v[i].second + v[j].second) / 2};

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

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