Cod sursa(job #2924407)

Utilizator miramaria27Stroie Mira miramaria27 Data 1 octombrie 2022 18:59:43
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>

using namespace std;

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

double distance(pair<double, double> l1, pair<double, double> l2) {
  return (l1.first - l2.first) * (l1.first - l2.first) +
         (l1.second - l2.second) * (l1.second - l2.second);
}

bool areEqual(double d1, double d2) { return fabs(d1 - d2) < 0.01; }

bool checkTriang(pair<double, double> A, pair<double, double> B,
                 pair<double, double> C) {
  double y = distance(B, C);
  return areEqual(distance(A, B), y) && areEqual(y, distance(A, C));
}

bool equalPairs(pair<double,double>p1, pair<double,double>p2){
  return p1.first == p2.first && p1.second == p2.second;
}

bool binarySearch(int i, int j, int left,
                  int right, vector<pair<double, double>> &coord) {
  if (left <= right) {
    int mid = left + (right - left) / 2;
    pair<double, double> C = coord[mid];
    pair<double, double> A = coord[i];
    pair<double, double> B = coord[j];
    if (checkTriang(A, B, C) && mid !=i && mid!=j) {
      return true;
    }
    if (distance(A, B) < distance(B, C)) {
      return binarySearch(i,j, left, mid - 1, coord);
    }
    return binarySearch(i,j, mid + 1, right, coord);
  }
  return false;
}

int main() {
  vector<pair<double, double>> coord;
  int N, nr = 0;
  fin >> N;
  for (int i = 0; i < N; i++) {
    double a, b;
    fin >> a >> b;
    coord.push_back(make_pair(a, b));
  }

  sort(coord.begin(), coord.end());
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      // we take each pair of points A, B
      // we want to find a point C for which A, B, C is an equilateral triangle
      // we use binary search to find this point
      if (binarySearch(i,j, 0, N, coord)) {
        nr += 1;
      };
    }
  fout << nr / 3;
}