Cod sursa(job #2781968)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 11 octombrie 2021 10:26:13
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

#define vector vector1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1

typedef long double ld;

class vector {
public:
  ld x;
  ld y;

  vector(ld x, ld y) : x(x), y(y) {
  }

  vector() {

  }

};

const ld eps = 1e-14;

vector operator - (vector a) {
  return vector(-a.x, -a.y);
}

vector operator - (vector a, vector b) {
  return vector(a.x - b.x, a.y - b.y);
}

vector perpendicular(vector a) {
  return vector(-a.y, a.x);
}

ld dot(vector a, vector b) {
  return a.x * b.x + a.y * b.y;
}

ld cross(vector a, vector b) {
  return a.y * b.x - a.x * b.y;
}

int getSign(ld value) {
  if (abs(value) < eps) {
    return 0;
  }
  if (value >= -eps) {
    return 1;
  } else {
    return -1;
  }
}

ld paralelogram(vector a, vector b, vector c) {
  return cross(b - a, c - a);
}




const int N = 120000 + 7;
int n;
vector a[N];
vector stk[N];
int sz;

bool cmp(vector ff, vector ss) {
  return getSign(paralelogram(a[1], ff, ss)) == -1;
}


int main() {
  freopen ("infasuratoare.in", "r", stdin);
  freopen ("infasuratoare.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y;
    if (a[i].x < a[1].x || (a[i].x == a[1].x && a[i].y < a[1].y)) swap(a[i], a[1]);
  }
  sort(a + 2, a + n + 1, cmp);
  a[n + 1] = a[1];

  for (int i = 1; i <= n + 1; i++) {
    vector pt = a[i];
    while (sz >= 2 && getSign(paralelogram(stk[sz - 1], stk[sz], pt)) >= 0) {
      sz--;
    }
    stk[++sz] = pt;
  }

  sz--;
  cout << sz << "\n";

  for (int i = 1; i <= sz; i++) {
    cout << fixed << setprecision(12) << stk[i].x << " " << stk[i].y << "\n";
  }


  return 0;
}