Cod sursa(job #2757207)

Utilizator marquiswarrenMajor Marquis Warren marquiswarren Data 4 iunie 2021 15:27:18
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <complex>
#include <cmath>
#include <algorithm>

#define _USE_MATH_DEFINES

using namespace std;

const int NMAX = 1505;
complex<double> pt[NMAX];
int N;

const double EPS = 1e-5;

void read() {
	ifstream f("triang.in");
	f >> N;
	for (int i = 1; i <= N; i++) {
		double x, y;
		f >> x >> y;
		pt[i] = complex<double>(x, y);
	}
}

complex<double> rotate(const complex<double>& z, double u) {
	return z * exp(1i * u);
}

bool exists(const complex<double>& z, int s) {
	return binary_search(
		pt + s,
		pt + N + 1,
		z,
		[](const auto& z1, const auto& z2) -> bool{
			if (abs(real(z1) - real(z2)) <= EPS)
				return abs(imag(z1) - imag(z2)) > EPS;
			return abs(real(z1) - real(z2)) > EPS;
		}
	);
}

void solve() {
	int triangles = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = i+1; j <= N; j++) {
			auto z = pt[j] - pt[i];

			for (const double u: {M_PI/3, -M_PI/3}) {
				auto rot = rotate(z, u);
				auto c = pt[j] - rot;

				if (exists(c, j)) ++triangles;
			}
		}
	}

	ofstream g("triang.out");
	g << triangles;
}

int main() {
	read();	

	sort(pt + 1, pt + N + 1, [](const auto& z1, const auto& z2) -> bool {
		if (abs(real(z1) - real(z2)) < EPS)
			return imag(z1) < imag(z2);
		return real(z1) < real(z2);
	});

	solve();
}