Cod sursa(job #2605558)

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

#define NMAX 1500

using namespace std;

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

struct pct {
	float x, y;
};

struct dist {
	int i, j;
	float d;
};

float mat[NMAX][NMAX];
pct v[NMAX];
int n, m;
dist d[NMAX * NMAX];

bool cmp(dist d1, dist d2) {
	return (d1.d < d2.d);
}

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

void init() {
	fin >> n;
	for (int i = 0;i < n;++i)
		fin >> v[i].x >> v[i].y;
	m = 0;
	for(int i=0;i<n;++i)
		for (int j = i + 1;j < n;++j) {
			mat[i][j] = mat[j][i] = distance(v[i], v[j]);
			d[m++] = { i,j,mat[i][j] };
		}
	sort(d, d + m, cmp);
}

int search(float D) {
	int low = 0, high = m - 1;
	while (low <= high) {
		int mid = low + (high - low) / 2;
		if (d[mid].d == D && d[mid + 1].d != D) return mid;
		if (d[mid].d <= D)
			low = mid + 1;
		else
			high = mid - 1;
	}
	return -1;
}

int solve() {
	int nr = 0;
	for (int i = 0;i < m;++i) {
		int k = search(d[i].d);
		while (d[k].d == d[i].d && k>i) {
			if (d[k].i == d[i].i && mat[d[k].j][d[i].j] == d[i].d) ++nr;
			else if (d[k].i == d[i].j && mat[d[k].j][d[i].i] == d[i].d) ++nr;
			else if (d[k].j == d[i].i && mat[d[k].i][d[i].j] == d[i].d) ++nr;
			else if (d[k].j == d[i].j && mat[d[k].i][d[i].i] == d[i].d) ++nr;
			--k;
		}
	}
	return nr/3;
}

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

	return 0;
}