Cod sursa(job #2891104)

Utilizator matthriscuMatt . matthriscu Data 17 aprilie 2022 15:47:39
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
using std::pair;
using std::sort;

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

inline ld 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);
}

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

inline 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()
{
	FILE *in = fopen("triang.in", "r");

	int n;
	fscanf(in, "%d", &n);

	pair<ld, ld> v[NMAX];
	for (int i = 1; i <= n; ++i)
		fscanf(in, "%Lf%Lf", &v[i].first, &v[i].second);
	
	fclose(in);
	
	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 = neg_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);
		}

	FILE *out = fopen("triang.out", "w");
	fprintf(out, "%lld\n", ans / 3);
	fclose(out);
}