Cod sursa(job #2890642)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 16 aprilie 2022 10:49:29
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

using namespace std;
// using namespace __gnu_pbds;
// template<typename T>
// using oset = tree<T, null_type, less<T>,
				  // rb_tree_tag, tree_order_statistics_node_update>;

#define nl cout.put('\n')
using ll = long long;
using ull = unsigned long long;

#ifdef Wi_TEST
	template<typename T1, typename T2>
	ostream& operator<<(ostream& out, pair<T1,T2> p) {
		out << "(" << p.first << ", " << p.second << ")";
		out.flush(); return out;
	}
	void DEB() { cerr << "]" << endl; }
	template<typename H, typename ... T>
	void DEB(H h, T... t) {
		cerr << h;
		if(sizeof...(t)) cerr << ", ";
		DEB(t...);
	}
	#define deb(...) cerr << "LINE(" << __LINE__ << ") -> [" << \
						     #__VA_ARGS__ << "]: [", DEB(__VA_ARGS__)
#else
	#define deb(...) 87105
#endif

const long long MOD = 1000000007, MOD2 = 998244353;
int lx[] = {0, 1, 0, -1}, ly[] = {1, 0, -1, 0};

#define N 1505

int n;
pair<double, double> v[N];

pair< pair<double, double>, pair<double, double> >
compute_third(pair<double, double>& a, pair<double, double>& b) {
	pair< pair<double, double>, pair<double, double> > p;
	p.first = make_pair((a.first + b.first + sqrt(3) * (a.second - b.second)) * 0.5,
						(a.second + b.second - sqrt(3) * (a.first - b.first)) * 0.5);
	p.second = make_pair((a.first + b.first - sqrt(3) * (a.second - b.second)) * 0.5,
						 (a.second + b.second + sqrt(3) * (a.first - b.first)) * 0.5);
	return p;
}

bool check_exist(pair<double, double> p, const double& prec) {
	int a = 0, b = n - 1, mid;
	while (a <= b) {
		mid = (a + b) / 2;
		if (fabs(p.first - v[mid].first) < prec &&
			fabs(p.second - v[mid].second) < prec)
			return true;
		else if(p.first + prec <= v[mid].first ||
				(fabs(p.first - v[mid].first) < prec &&
				 p.second + prec <= v[mid].second))
			b = mid - 1;
		else
			a = mid + 1;
	}
	return false;
}

void solve() {
	ifstream fin("triang.in");
	ofstream fout("triang.out");
	
	const double prec = 0.001;
	int rez = 0;
	fin >> n;
	for (int i = 0; i < n; ++i) {
		fin >> v[i].first >> v[i].second;
	}
	sort(v, v+n);
	for (int i = 0; i < n - 1; ++i) {
		for (int j = i + 1; j < n; ++j) {
			pair< pair<double, double>, pair<double, double> > p =
				compute_third(v[i], v[j]);
			rez += check_exist(p.first, prec) +
				   check_exist(p.second, prec);
			// deb(p.first.first, p.first.second);
			// deb(p.second.first, p.second.second);
		}
	}
	fout << rez / 3;
}

int main() {
	ios_base::sync_with_stdio(false);
#ifndef Wi_TEST
	cin.tie(0);
#endif
	
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; ++i) {
		solve();
	}
}