Cod sursa(job #2890597)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 15 aprilie 2022 23:59:35
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 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 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);
	}

	int st = j + 1, dr = n, mij, poz1 = -1, poz2 = -1;

	while (st <= dr)
	{
		mij = st + (dr - st) / 2;
		if (diff(p1, v[mij]) < eps) {
			poz1 = mij;
			dr = st - 1;
		} else if (v[mij] < p1) {
			st = mij + 1;
		} else {
			dr = mij - 1;
		}
	}

	while (st <= dr)
	{
		mij = st + (dr - st) / 2;
		if (diff(p2, v[mij]) < eps) {
			poz2 = mij;
			dr = st - 1;
		} else if (v[mij] < p2) {
			st = mij + 1;
		} else {
			dr = mij - 1;
		}
	}

	return (((int)(poz1 != -1)) + ((int)(poz2 != -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;
}