Cod sursa(job #2700309)

Utilizator retrogradLucian Bicsi retrograd Data 27 ianuarie 2021 12:32:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

using Point = complex<double>;
using Poly = vector<Point>;
const double EPS = 1e-12;

double cross(Point a, Point b) {
  return a.real() * b.imag() - a.imag() * b.real(); 
}
double det(Point a, Point b, Point c) {
  return cross(b - a, c - a);
}

namespace std {
  bool operator<(const Point a, const Point b) {
    return make_pair(a.real(), a.imag()) <
      make_pair(b.real(), b.imag());
  }
}

Poly HullHalf(Poly& P, int z) {
  Poly ret;
  for (auto p : P) {
    while ((int)ret.size() >= 2 && 
        z * det(ret.end()[-2], ret.end()[-1], p) < EPS)
      ret.pop_back();
    ret.push_back(p);
  }
  return ret;
}
Poly Hull(Poly P) {
  sort(P.begin(), P.end());
  P.erase(unique(P.begin(), P.end()), P.end());
  auto l = HullHalf(P, +1), u = HullHalf(P, -1); 
  l.insert(l.end(), u.rbegin() + 1, u.rend() - 1);
  return l;
}

int main() {
  ifstream cin("infasuratoare.in");
  ofstream cout("infasuratoare.out");
  int n; cin >> n;
  vector<Point> P;
  for (int i = 0; i < n; ++i) {
    double x, y; cin >> x >> y;
    P.emplace_back(x, y);
  }
  auto H = Hull(P);
  cout << fixed << setprecision(12);
  cout << H.size() << '\n';
  for (auto p : H) 
    cout << p.real() << " " << p.imag() << '\n';
  
  return 0;
}