Cod sursa(job #2890598)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 16 aprilie 2022 00:15:37
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>
#define NMAX 1505

using namespace std;

int n;
pair <double, double> v[NMAX], p;
const double eps = 0.0001;

inline double sq(double x)
{
	return (x * x);
}

inline double diff(pair<double, double> a, pair <double, double> b)
{
	return (abs(a.first - b.first) + abs(a.second - b.second));
}

int find_point(pair<double, double> p, int poz)
{
	int st = poz, dr = n, mij;

	while (st <= dr)
	{
		mij = st + ((dr - st) >> 1);
		if (diff(p, v[mij]) < eps)
			return 1;
		else if (v[mij] < p)
			st = mij + 1;
		else
			dr = mij - 1;
	}

	return 0;
}

int count_ech(int i, int j)
{
	double x1 = v[i].first;
	double y1 = v[i].second;

	double x2 = v[j].first;
	double y2 = v[j].second;

	double xm = (x1 + x2) / 2;
	double ym = (y1 + y2) / 2;

	double l_sq = sq(x2 - x1) + sq(y2 - y1);

	pair <double, double> p1, p2;
	if (y2 == y1) {
		double aux = sqrt(3 * l_sq / 4);

		p1.first = xm;
		p1.second = ym + aux;

		p2.first = xm;
		p2.second = ym - aux;
	} else {
		double m2 = (x1 - x2) / (y2 - y1);
		double aux = sqrt((3 * l_sq) / (4 * (sq(m2) + 1)));

		p1.first = xm + aux;
		p1.second = ym + m2 * (p1.first - xm);

		p2.first = xm - aux;
		p2.second = ym + m2 * (p2.first - xm);
	}

	return (find_point(p1, j + 1) + find_point(p2, j + 1));
}

int main()
{
	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);

	cin >> n;

	for (int i = 1; i <= n; ++i)
		cin >> v[i].first >> v[i].second;

	sort(v + 1, v + n + 1);

	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = i + 1; j <= n; ++j)
			cnt += count_ech(i, j);

	cout << cnt << '\n';
	return 0;
}