Cod sursa(job #2605766)

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

#define NMAX 1500
#define EPSILON 1e-3

using namespace std;

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

struct pct {
	double x, y;
};

struct Pair {
	int k;
	double d;
};

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

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

double dist(pct &a, pct &b) {
	double 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) {
			double 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(int i,double d) {
	int low = 0, high = n - 2;
	while (low <= high) {
		int mid = low + (high - low) / 2;
		if (abs(mat[i][mid].d - d) < EPSILON && (mid==n-2 || abs(mat[i][mid + 1].d - d) > EPSILON))
			return mid;
		if (mat[i][mid].d < d || abs(mat[i][mid].d - d) < EPSILON)
			low = mid + 1;
		else
			high = mid - 1;
	}
	return -1;
}

int search2(int i, double d) {
	int low = 0, high = n - 2;
	while (low <= high) {
		int mid = low + (high - low) / 2;
		if (abs(mat[i][mid].d - d) < EPSILON && (mid == 0 || abs(mat[i][mid - 1].d - d) > EPSILON))
			return mid;
		if (mat[i][mid].d < d)
			low = mid + 1;
		else
			high = mid - 1;
	}
	return -1;
}

int solve() {
	int nr = 0;
	for(int i=0;i<n;++i)
		for (int j = i + 1;j < n;++j) {
			double d = dist(v[i], v[j]);
			int k1 = search(i, d), k2 = search2(i, d);
			nr += k1 - k2 - 1;
		}
	return nr/3;
}

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

	return 0;
}