Cod sursa(job #2755459)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 27 mai 2021 12:39:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

const int NMAX = 12e4;

class Point {
public:
  double x, y;

  Point() = default;
};

Point a[1 + NMAX];

std::vector<int> stack;

inline double ccw(const Point& origin, const Point& A, const Point& B) {
  double ax = A.x - origin.x;
  double ay = A.y - origin.y;

  double bx = B.x - origin.x;
  double by = B.y - origin.y;

  return ax * by - ay * bx;
}

inline double distSqr(const Point& A, const Point& B) {
  return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

bool cmp_ccw(const Point& A, const Point& B) {
  double _ccw = ccw(a[1], A, B);
  /*
   if (_ccw == 0)
     return distSqr(a[1], A) < distSqr(a[1], B);
 */
  return _ccw > 0;
}

int main() {
  std::ifstream in("infasuratoare.in");
  std::ofstream out("infasuratoare.out");

  int n;
  in >> n;

  int minIdx = 1;
  for (int i = 1; i <= n; ++i) {
    in >> a[i].x >> a[i].y;

    if (a[i].x < a[minIdx].x || (a[i].x == a[minIdx].x && a[i].y < a[minIdx].y))
      minIdx = i;
  }

  std::swap(a[1], a[minIdx]);

  std::sort(a + 2, a + 1 + n, cmp_ccw);

  stack.reserve(n);
  stack.push_back(1);
  stack.push_back(2);

  for (int i = 3; i <= n; ++i) {
    while (stack.size() >= 2 && ccw(a[stack[stack.size() - 2]], a[stack[stack.size() - 1]], a[i]) <= 0)
      stack.pop_back();

    stack.push_back(i);
  }

  out << stack.size() << '\n';
  for (auto& idx : stack)
    out << std::fixed << std::setprecision(6) << a[idx].x << ' ' << a[idx].y << '\n';

  return 0;
}