Cod sursa(job #2374586)

Utilizator GoogalAbabei Daniel Googal Data 7 martie 2019 19:29:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

#define err 1e-12

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const int NMAX = 12 * 1e4;

struct Point {
  double x;
  double y;

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

int n;
int minn = -1;

int last;
int st[1 + NMAX];

Point v[1 + NMAX];

double det(Point a, Point b, Point c) {
  double plus = a.x * b.y + b.x * c.y + a.y * c.x;
  double minus = c.x * b.y + a.y * b.x + a.x * c.y;

  return (plus - minus);
}

bool cmp(Point b, Point c){
  Point a = v[1];
  return ((det(a, b, c)) < 0);
}

int main()
{
  in >> n;

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

    if(v[i] < v[minn])
      minn = i;
  }

  swap(v[1], v[minn]);

  sort(v + 2, v + n + 1, cmp);

  st[1] = 1;
  st[2] = 2;
  last = 2;

  for(int i = 3; i <= n; i++){
    while(last >= 2 && det(v[st[last - 1]], v[st[last]], v[i]) > 0)
      last--;
    st[++last] = i;
  }

  out << last << '\n';

  out << setprecision(6) << fixed;

  for(int i = last; i >= 1; i--){
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
  }

  in.close();
  out.close();

  return 0;
}