Cod sursa(job #2592653)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 2 aprilie 2020 00:03:10
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;

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

typedef pair <double, double> p;

const double eps = 1e-4;

vector <p> v;

int n, cnt;

inline bool equal(double d)
{
	return fabs(d) < eps;
}


inline double compute_distance(p a, p b)
{
	double x = a.x - b.x, y = a.y - b.y;
	return sqrt(3 * (x * x + y * y)) / 2;
}

bool b_search(int c_s, double xc, double yc)
{
	int st = c_s, dr = n;
	while (st <= dr)
	{
		int mid = ((st + dr) >> 1);
		if (equal(v[mid].x - xc))
		{
			if (equal(v[mid].y - yc))
				return 1;
			if (v[mid].y > yc)
				dr = mid - 1;
			else st = mid + 1;
		}
		else if (v[mid].x < xc)
			dr = mid - 1;
		else st = mid + 1;
	}
	return 0;
}

int main()
{
	fin >> n;
	v.resize(n + 1);
	for (int i = 1; i <= n; ++i)
		fin >> v[i].x >> v[i].y;

	sort(v.begin() + 1, v.end());

	for (int i = 1; i < n - 1; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			double d = compute_distance(v[i], v[j]), xm = (v[i].x + v[j].x) / 2, ym = (v[i].y + v[j].y) / 2;

			if (equal(v[i].y - v[j].y))
			{
				double yc1 = v[i].y + d;
				double yc2 = v[i].y - d;
				cnt += b_search(j + 1, xm, yc1);
				cnt += b_search(j + 1, xm, yc2);
			}

			else
			{
				double m = (v[j].x - v[i].x) / (v[i].y - v[j].y);
				d *= d;
				double r = sqrt(d / (m * m + 1));
				double xc = xm + r;
				double yc = m * (xc - xm);
				yc += ym;
				cnt += b_search(j + 1, xc, yc);
				xc = xm - r;
				yc = m * (xc - xm) + ym;
				cnt += b_search(j + 1, xc, yc);
			}
		}
	}

	fout << cnt << "\n";

	return 0;
}