Cod sursa(job #2781944)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 11 octombrie 2021 09:54:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <bits/stdc++.h>

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 dot(a, perpendicular(b));
}

int getSign(ld value) {
  if (fabs(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);
}

bool onSegment(vector a, vector b, vector p) {
  return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool intersectSegment(vector p1, vector p2, vector p3, vector p4) {
  int dir1 = getSign(paralelogram(p3, p4, p1));
  int dir2 = getSign(paralelogram(p3, p4, p2));
  int dir3 = getSign(paralelogram(p1, p2, p3));
  int dir4 = getSign(paralelogram(p1, p2, p4));


  if (dir1 * dir2 == -1 && dir3 * dir4 == -1) {
    return 1;
  }

  if (dir1 == 0 && onSegment(p3, p4, p1)) return 1;
  if (dir2 == 0 && onSegment(p3, p4, p2)) return 1;
  if (dir3 == 0 && onSegment(p1, p2, p3)) return 1;
  if (dir4 == 0 && onSegment(p1, p2, p4)) return 1;

  return 0;
}

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[0], ff, ss)) >= 0;
}

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)) == -1) {
      sz--;
    }
    stk[++sz] = pt;
  }

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


  return 0;
}