Cod sursa(job #2782002)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 11 octombrie 2021 12:35:31
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.89 kb
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <cassert>
#include <vector>

using namespace std;

typedef long double ld;

class ve {
public:
  ld x;
  ld y;

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

  ve() {

  }

};

const ld eps = 1e-14;

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

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

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

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

ld cross(ve a, ve 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(ve a, ve b, ve c) {
  return cross(b - a, c - a);
}

bool operator < (ve a, ve b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}

bool sub(set<ve> &hull, ve pt) {
  auto it = hull.lower_bound(pt);
  if (it == hull.end()) {
    return 0;
  }
  if (it == hull.begin()) {
    return (it->x == pt.x);
  }
  ve nxt = *it;
  it--;
  ve ant = *it;
  return getSign(cross(nxt - pt, ant - pt)) <= 0;
}

bool concav(set<ve> &hull, set<ve>::iterator it) {
  if (it == hull.begin() || it == hull.end()) return 0;
  ve now = *it;
  it--;
  ve ant = *it;
  it++;
  it++;

  if (it == hull.end()) return 0;
  ve nxt = *it;
  return getSign(cross(nxt - now, ant - now)) <= 0;
}

void ins(set<ve> &hull, ve pt) {
  if (sub(hull, pt)) return;
  hull.insert(pt);
  auto it = hull.find(pt);
  it++;

  while (concav(hull, it)) {
    ve now = *it;
    it++;
    hull.erase(now);
  }
  it = hull.find(pt);
  assert(it != hull.end());
  if (it != hull.begin()) {
    it--;
  }
  while (concav(hull, it)) {
    ve now = *it;
    it--;
    hull.erase(now);
  }
}

int main() {
  freopen ("infasuratoare.in", "r", stdin);
  freopen ("infasuratoare.out", "w", stdout);

  //cout << fixed << setprecision(12);

  set<ve> low, high;
  int n;
  cin >> n;
  while (n--) {
    ve pt;
    cin >> pt.x >> pt.y;
    ins(low, pt);
    ins(high, -pt);
  }
 // return 0;

  vector<ve> a, b;
  for (auto &it : low) {
    a.push_back(it);
  }
  for (auto &it : high) {
    b.push_back(-it);
  }
  b.pop_back();
  if (!b.empty() && a.back().x == b[0].x && a.back().y == b[0].y) {
    a.pop_back();
  }
  vector<ve> all;
  for (auto &it : a) {

  ///  cout << fixed << setprecision(12) << it.x << " " << it.y << "\n";
    all.push_back(it);
  }
///  cout << "\n";
  for (auto &it : b) {

   /// cout << fixed << setprecision(12) << it.x << " " << it.y << "\n";
    all.push_back(it);
  }
  ///return 0;
  reverse(all.begin(), all.end());
  cout << (int) all.size() << "\n";
  for (auto &it : all) {
    cout << fixed << setprecision(12) << it.x << " " << it.y << "\n";
  }
  return 0;
}