Cod sursa(job #2202950)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 10 mai 2018 15:30:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 5.08 kb
#include <bits/stdc++.h>
  
const double kEps = 1e-6;
  
bool Equals(double a, double b) {
  return fabs(a - b) < kEps;
}
  
struct Point {
  Point() : x(0.0), y(0.0) {}
  
  Point(double x, double y) : x(x), y(y) {}
  
  double CrossProduct(const Point& b, const Point& c) const {
    return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);
  }
  
  double Distance(const Point& b, const Point& c) const {
    return fabs((c.y - b.y) * x - (c.x - b.x) * y + c.x * b.y - c.y * b.x) /
           sqrt((c.y - b.y) * (c.y - b.y) + (c.x - b.x) * (c.x - b.x));
  }
  
  bool InTriangle(const Point& a, const Point& b, const Point& c) const {
    bool c1 = CrossProduct(a, b) < 0.0;
    bool c2 = CrossProduct(b, c) < 0.0;
    bool c3 = CrossProduct(c, a) < 0.0;
  
    return (c1 == c2) && (c2 == c3);
  }
  
  bool operator == (const Point& b) const {
    return Equals(x, b.x) && Equals(y, b.y);
  }
  
  bool operator != (const Point& b) const {
    return !(*this == b);
  }
  
  double x, y;
};
  
std::vector<Point> ReadPoints(const std::string& input_file) {
  std::ifstream fin(input_file);
  
  int num_points;
  fin >> num_points;
  
  std::vector<Point> points;
  for (int i = 0; i < num_points; i++) {
    double x, y;
    fin >> x >> y;
    points.emplace_back(x, y);
  }
  
  return points;
}
  
std::vector<Point> SolveQuickHull(const Point& low_point,
                                  const Point& high_point, const std::vector<Point>& candidates) {
  if (candidates.empty()) {
    return std::vector<Point>();
  }
  
  double best_distance = 0.0;
  Point best_point;
  for (const Point& point : candidates) {
    double point_distance = point.Distance(low_point, high_point);
    if (point_distance > best_distance) {
      best_distance = point_distance;
      best_point = point;
    }
  }
  
  std::vector<Point> left_side;
  std::vector<Point> right_side;
  for (const Point& point : candidates) {
    if (point != best_point) {
      if (point.InTriangle(low_point, high_point, best_point)) {
        continue;
      }
  
      if (point.CrossProduct(low_point, best_point) > 0) {
        left_side.push_back(point);
      } else {
        right_side.push_back(point);
      }
    }
  }
  
  /* std::cout << best_point.x << " " << best_point.y << '\n'; */
  /* for (auto it : left_side) { */
  /*   std::cout << it.x << " " << it.y << " "; */
  /* } */
  /* std::cout << '\n'; */
  /* for (auto it : right_side) { */
  /*   std::cout << it.x << " " << it.y << " "; */
  /* } */
  /* std::cout << '\n'; */
  /* std::cout << "------------------------\n"; */
  
  std::vector<Point> left_convex_hull = SolveQuickHull(high_point, best_point,
                                        left_side);
  std::vector<Point> right_convex_hull = SolveQuickHull(low_point, best_point,
                                         right_side);
  
  std::vector<Point> convex_hull;
  convex_hull.insert(convex_hull.end(), left_convex_hull.begin(),
                     left_convex_hull.end());
  convex_hull.push_back(best_point);
  convex_hull.insert(convex_hull.end(), right_convex_hull.begin(),
                     right_convex_hull.end());
  return convex_hull;
}
  
std::vector<Point> QuickHull(const std::vector<Point>& points) {
  int num_points = points.size();
  
  Point low_point = *points.begin();
  Point high_point = *points.begin();
  for (const Point& point : points) {
    if (point.y < low_point.y) {
      low_point = point;
    }
    if (point.y > high_point.y) {
      high_point = point;
    }
  }
  
  std::vector<Point> left_side;
  std::vector<Point> right_side;
  for (const Point& point : points) {
    if (point != low_point && point != high_point) {
      double cross_product = point.CrossProduct(high_point, low_point);
      if (Equals(cross_product, 0.0)) {
        continue;
      }
      if (cross_product < 0) {
        left_side.push_back(point);
      } else {
        right_side.push_back(point);
      }
    }
  }
  
  std::vector<Point> left_convex_hull = SolveQuickHull(low_point, high_point,
                                        left_side);
  std::vector<Point> right_convex_hull = SolveQuickHull(low_point, high_point,
                                         right_side);
  
  std::vector<Point> convex_hull;
  convex_hull.insert(convex_hull.end(), left_convex_hull.begin(),
                     left_convex_hull.end());
  convex_hull.push_back(high_point);
  convex_hull.insert(convex_hull.end(), right_convex_hull.begin(),
                     right_convex_hull.end());
  convex_hull.push_back(low_point);
  return convex_hull;
}
  
int main(int argc, char** argv) {
  /* if (argc != 2) { */
  /*   std::cout << "Usage: ./seq <input_file> <output_file>" << '\n'; */
  /*   exit(1); */
  /* } */
  
  /* auto points = ReadPoints(std::string(argv[1])); */
  auto points = ReadPoints(std::string("infasuratoare.in"));
  auto convex_hull = QuickHull(points);
  
  std::ofstream fout("infasuratoare.out");
  std::reverse(convex_hull.begin(), convex_hull.end());
  fout << convex_hull.size() << '\n';
  for (const Point& point : convex_hull) {
    fout << std::fixed << std::setprecision(6)
              << point.x << " " << point.y << '\n';
  }
  
  return 0;
}