Cod sursa(job #2891892)

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

using namespace std;

#define x first
#define y second

#define eps 0.001
#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;
}

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 cmp(pair<double, double> a, pair<double, double> b)
{
	if (abs(a.x - b.x) + abs(a.y - b.y) < eps)
		return 1;
	return 0;
}

int binary_search(int p, pair<double, double> s)
{
	int st = p + 1, dr = n, mij;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (cmp(v[mij], s) == 0) {
			cout << mij << " <-MIJ\n";
			cout << v[mij].x << ' ' << v[mij].y << '\n';
			cout << s.x << ' ' << s.y << '\n';
			return 1;
		}
		if (v[mij] < s)
			st = mij + 1;
		else
			dr = mij - 1;
	}
	return 0;
}

int possible_point(int index1, int index2)
{
	pair<double, double> z1, z2, mij;
	mij.x = (v[index1].x + v[index2].x) / 2;
	mij.y = (v[index1].y + v[index2].y) / 2;
	double d = dist[index1][index2] * 3 / 4;
	if (v[index1].y != v[index2].y) {
		cout << "NU EGALE\n";
		double p = (v[index1].x - v[index2].x) / (v[index1].y - v[index2].y);
		p = -p;
		z1.x = mij.x + sqrt(d / (p * p + 1));
		z1.y = mij.y + p * (z1.x - mij.x);

		z2.x = mij.x - sqrt(d / (p * p + 1));
		z2.y = mij.y + p * (z2.x - mij.x);
		cout << z1.x << ' ' << z1.y << ' ' << z2.x << ' ' << z2.y << '\n';
	} else {
		cout << "EGALE\n";
		z1.x = mij.x;
		z1.y = mij.y + sqrt(d);
		z2.x = mij.x;
		z2.y = mij.y - sqrt(d);
		cout << z1.x << ' ' << z1.y << ' ' << z2.x << ' ' << z2.y << '\n';
	}
	int nr = binary_search(index2, z1);
	nr += binary_search(index2, z2);
	cout << nr << " <- NR\n";
	return nr;
}

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);
	for (int i = 1; i <= n; i++)
		cout << v[i].x << ' ' << v[i].y << '\n';
	precalc();
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			cnt += possible_point(i, j);
	cout << cnt << '\n';
	fout << cnt << '\n';
	fin.close();
	fout.close();
	return 0;
}