Cod sursa(job #2891879)

Utilizator mateicalin2002Ceausu Matei Calin mateicalin2002 Data 20 aprilie 2022 01:48:14
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

#define eps 1e-3
#define NMAX 1505

pair<double, double> v[NMAX];

int n;
double dist[NMAX][NMAX];

double pit(double a, double b)
{
	return a*a + b*b;
}

int cmp(double a, double b)
{
	if (a - b > eps)
		return 1;
	if (a - b < -eps)
		return -1;
	return 0;
}

void precalc()
{
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) {
			dist[i][j] = pit(v[i].x - v[j].x, v[i].y - v[j].y); 
			dist[j][i] = dist[i][j];
		}
}

int check(int index1, int index2, int index3)
{
	if (!cmp(dist[index1][index3], dist[index2][index3]))
		if (!cmp(dist[index1][index3], dist[index1][index2]))
			return 1;
	return 0;
}

int binary_search(int index1, int index2)
{
    int i, step;
    for (step = 1; step <= n; step <<= 1);
    for (i = max(index1, index2); step; step >>= 1)
        if (i + step <= n && check(index1, index2, i + step))
           i += step;
    return i;
}

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

	int cnt = 0;
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> v[i].x >> v[i].y;
	sort(v + 1, v + n + 1);
	precalc();
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) {
			int r = binary_search(i, j);
			//cout << r << " <- R\n\n";
			if (check(i, j, r) == 1)
				++cnt;
		}
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << dist[i][j] << ' ';
		cout << '\n';
	}*/
	fout << cnt << '\n';
	fin.close();
	fout.close();
	return 0;
}