Cod sursa(job #2846835)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 9 februarie 2022 18:30:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

#define all(a) a.begin(), a.end()
#define range(a, l, r) a.begin() + l, a.begin() + r
#define aall(a, n) a + 1, a + 1 + n
#define arange(a, l, r) a + l, a + r
	
#define maxself(a, b) a = std::max(a, b);
#define minself(a, b) a = std::min(a, b);

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

const int NMAX = 1.2e5;

class Point {
public:
  long double x, y;

  Point() = default;
};

int n;
Point a[1 + NMAX];

std::vector<int> stack;

inline long double ccw(const Point& origin, const Point &A, const Point &B) {
  return (A.x - origin.x) * (B.y - origin.y) - (B.x - origin.x) * (A.y - origin.y);
}

bool ccwSort(const Point& i, const Point& j) {
  return ccw(a[1], i, j) > 0;
}

int main() {
  inout("infasuratoare");

  in >> n;

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

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

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

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

  stack.push_back(1);

  for (int i = 2; 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 (int i : stack)
    out << std::fixed << std::setprecision(6) << a[i].x << ' ' << a[i].y << '\n';

  return 0;
}