Cod sursa(job #1551581)

Utilizator bolovMihail Balan bolov Data 16 decembrie 2015 01:10:15
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <cmath>

#include <iostream>

#include <fstream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;
using std::endl;

struct Point {
  double x, y;
};

static auto get_square_dist(Point const &p1, Point const &p2) -> double {
  return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
static auto get_dist(Point const &p1, Point const &p2) -> double {
  return std::sqrt(get_square_dist(p1, p2));
}

static auto const epsilon = 0.001;
static auto const degrees_60 =
    1.0471975511965977461542144610931676280657231331250352;
// static auto are_equal_epsilon(double a, double b) -> bool {
//   return std::abs(a - b) < epsilon;
// }
static auto are_equal_epsilon(Point pa, Point pb) -> bool {
  return std::abs(pa.x - pb.x) < epsilon && std::abs(pa.y - pb.y) < epsilon;
  // return get_square_dist(pa, pb) < epsilon * epsilon;
}

// given two points p1 and p2 with p2.x > p1.x
// returns the 3rd point to form an equilateral triangle.
// From the two such possible choices returns the rightmost;
static auto get_3rd_point(Point const &p1, Point const &p2) -> Point {
  auto const angle_12 = std::atan2(p2.y - p1.y, p2.x - p1.x);
  auto const dist = get_dist(p1, p2);

  auto const angle_13 =
      (angle_12 > 0) ? angle_12 - degrees_60 : angle_12 + degrees_60;

  return {p1.x + dist * std::cos(angle_13), p1.y + dist * std::sin(angle_13)};
}

using const_points_iterator = std::vector<Point>::const_iterator;

auto contains(const_points_iterator first, const_points_iterator last,
              const Point &p) -> bool {
  while (first < last) {
    auto const mid = first + (last - first) / 2;
    if (are_equal_epsilon(*mid, p))
      return true;

    if (p.x < mid->x)
      last = mid;
    else
      first = mid + 1;
  }
  return false;
}

std::ostream &operator<<(std::ostream &os, Point const &p) {
  os << "(" << p.x << ", " << p.y << ")";
  return os;
}

auto main() -> int {
  std::ifstream fin{"triang.in"};
  auto points = std::vector<Point>();

  auto n = int{};
  fin >> n;
  auto const size = n;
  points.reserve(size);

  for (auto i = 0; i < size; ++i) {
    Point p;
    fin >> p.x >> p.y;
    points.emplace_back(p);
  }
  fin.close();

  auto num = 0;

  std::sort(std::begin(points), std::end(points),
            [](Point const &p_a, Point const &p_b) { return p_a.x < p_b.x; });

  for (auto i = 0; i < size; ++i) {
    for (auto j = i + 1; j < size; ++j) {
      auto p3 = get_3rd_point(points[i], points[j]);
      if (p3.x < points[j].x)
        continue;

      if (contains(points.cbegin() + j + 1, points.cend(), p3)) {
        // cout << "triangle with vertices " << points[i] << ", " << points[j]
        //      << ", " << p3 << endl;
        ++num;
      }
    }
  }

  std::ofstream fout("triang.out");
  fout << num;

  return 0;
}