Cod sursa(job #2032931)

Utilizator preda.andreiPreda Andrei preda.andrei Data 5 octombrie 2017 21:32:00
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

const double kEps = 1e-12;
const double kInf = 1e12;

struct Point
{
  double x, y;

  bool operator==(const Point &other) const
  {
    return abs(x - other.x) < kEps && abs(y - other.y) < kEps;
  }

  bool operator<(const Point &other) const
  {
    if (abs(x - other.x) < kEps) {
      return y - other.y < kEps;
    }
    return x - other.x < kEps;
  }
};

inline bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
  auto delta = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
  return delta > 0;
}

Point Smallest(const vector<Point> &p)
{
  Point smallest { kInf, kInf };
  for (const auto &point : p) {
    smallest = min(smallest, point);
  }
  return smallest;
}

vector<Point> ConvexHull(vector<Point> &p)
{
  auto start = Smallest(p);
  auto cmp = [start] (const Point &a, const Point &b) -> bool {
    if (start == a) {
      return true;
    } else if (start == b) {
      return false;
    }
    return CounterClockwise(start, a, b);
  };

  sort(p.begin(), p.end(), cmp);

  vector<Point> hull;
  hull.push_back(p[0]);
  hull.push_back(p[1]);

  for (size_t i = 2; i < p.size(); ++i) {
    while (hull.size() > 1) {
      const auto &a = hull[hull.size() - 2];
      const auto &b = hull[hull.size() - 1];

      if (CounterClockwise(a, b, p[i])) {
        break;
      }
      hull.pop_back();
    }
    hull.push_back(p[i]);
  }
  return hull;
}

int main()
{
  ifstream fin("infasuratoare.in");
  ofstream fout("infasuratoare.out");

  int n;
  fin >> n;

  vector<Point> points(n);
  for (auto &p : points) {
    fin >> p.x >> p.y;
  }

  auto hull = ConvexHull(points);
  fout << hull.size() << "\n";

  for (const auto &p : hull) {
    fout << setprecision(13) << p.x << " " << p.y << "\n";
  }

  return 0;
}