Cod sursa(job #2605753)

Utilizator irimia_alexIrimia Alex irimia_alex Data 25 aprilie 2020 18:59:47
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>

#define NMAX 1500
#define EPSILON 1e-4

using namespace std;

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

struct pct {
	float x, y;
};

struct Pair {
	int k;
	float d;
};

int n;
vector<pct> v;
vector<Pair> mat[NMAX];

bool cmp(Pair& a, Pair& b) {
	return (a.d < b.d);
}

float dist(pct a, pct b) {
	float p1 = a.x - b.x, p2 = a.y - b.y;
	return p1 * p1 + p2 * p2;
}

void init() {
	fin >> n;
	pct p;
	for (int i = 0;i < n;++i) {
		fin >> p.x >> p.y;
		v.push_back(p);
	}
	for (int i = 0;i < n;++i) {
		for (int j = i+1;j < n;++j) {
			float d = dist(v[i], v[j]);
			mat[i].push_back({ j,d });
			mat[j].push_back({ i,d });
		}
		sort(mat[i].begin(), mat[i].end(), cmp);
	}
}

int search(vector<Pair> &m,float d) {
	int low = 0, high = n - 2;
	while (low <= high) {
		int mid = low + (high - low) / 2;
		if (abs(m[mid].d - d) < EPSILON && (mid==n-2 || abs(m[mid + 1].d - d) > EPSILON))
			return mid;
		if (m[mid].d < d || abs(m[mid].d - d) < EPSILON)
			low = mid + 1;
		else
			high = mid - 1;
	}
	return -1;
}

int solve() {
	int nr = 0;
	for(int i=0;i<n;++i)
		for (int j = 0;j < n - 1;++j) {
			int k = search(mat[i], mat[i][j].d);
			while (k >= 0 && abs(mat[i][k].d - mat[i][j].d) < EPSILON) {
				if(mat[i][k].k!=mat[i][j].k && abs(dist(v[mat[i][k].k],v[mat[i][j].k])-mat[i][j].d)<EPSILON)
					++nr;
				--k;
			}
		}
	return nr/6;
}

int main()
{
	init();
	fout << solve();

	return 0;
}