Cod sursa(job #2187604)

Utilizator NeredesinI am not real Neredesin Data 26 martie 2018 17:14:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#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, minn = 1;
int st[1 + NMAX], cnt;
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;
  }
  in.close();
  swap(v[1], v[minn]);
  sort(v + 2, v + n + 1, cmp);

  st[1] = 1;
  st[2] = 2;
  cnt = 2;

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

  out << cnt << '\n';
  out << setprecision(7) << fixed;
  for(int i = cnt; i >= 1; i--)
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';

  in.close();
  out.close();
  return 0;
}