Cod sursa(job #2146104)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 27 februarie 2018 19:50:43
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream in("triang.in");
ofstream out("triang.out");

// Scriere trigonometrica + translatarea punctelor in plan cu ajutorul afixelor scrise in complex

const double eps = 0.001;
const double cosinus = 0.5;
const double sinus = 0.8660;

bool Equal(double x, double y) {
	if(abs(x - y) < eps)
		return 1;
	return 0;
}

int main() {

	int n; in >> n;

	vector< pair< double, double > > puncte(n);
	for(int i = 0; i < n; ++i) {
		in >> puncte[i].first >> puncte[i].second;
	}

	sort(puncte.begin(), puncte.end());

	int ans = 0;
	for(int i = 0; i < n - 1; ++i) {
		for(int j = i + 1; j < n; ++j) {
			double Xc = puncte[i].first + (puncte[j].first - puncte[i].first) * cosinus - (puncte[j].second - puncte[i].second) * sinus;
			double Yc = puncte[i].second + (puncte[j].second - puncte[i].second) * cosinus + (puncte[j].first - puncte[i].first) * sinus;

			int lo = j + 1;
			int hi = n - 1;
			while(lo <= hi) {
				int mid = (lo + hi) / 2;
				if(Equal(puncte[mid].first, Xc) && Equal(puncte[mid].second, Yc)) {
					ans++;
					break;
				}
				if(Xc < puncte[mid].first || (Equal(Xc, puncte[mid].first) && Yc < puncte[mid].second)) {
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}

			Xc = puncte[i].first + (puncte[j].first - puncte[i].first) * cosinus + (puncte[j].second - puncte[i].second) * sinus;
			Yc = puncte[i].second + (puncte[j].second - puncte[i].second) * cosinus - (puncte[j].first - puncte[i].first) * sinus;

			lo = j + 1;
			hi = n - 1;
			while(lo <= hi) {
				int mid = (lo + hi) / 2;
				if(Equal(puncte[mid].first, Xc) && Equal(puncte[mid].second, Yc)) {
					ans++;
					break;
				}
				if(Xc < puncte[mid].first || (Equal(Xc, puncte[mid].first) && Yc < puncte[mid].second)) {
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
		}
	}

	out << ans << '\n';

    in.close(); out.close();
 
    return 0;
}