Cod sursa(job #2501590)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 29 noiembrie 2019 22:54:31
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

#define x first
#define y second
#define Point std::pair <double, double>

const int MAX_N = 120005;

int n;

int st[MAX_N];

std::pair <double, double> arr[MAX_N];

double cross_product(std::pair <double, double> a, std::pair <double, double> b,
                     std::pair <double, double> c) {
  return ((a.x * b.y) + (b.x * c.y) + (c.x * a.y) - (a.y * b.x) - (b.y * c.x) - (c.y * a.x));
}

int compare_points(const std::pair <double, double> &a, const std::pair <double, double> &b) {
  return (cross_product(arr[0], a, b) < 0);
}

int main() {
  int pos, k;
  double x_c, y_c;
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::cin >> x_c >> y_c;
    arr[i] = std::make_pair(x_c, y_c);
  }
  pos = 0;
  for (int i = 1; i < n; ++i) {
    if (arr[i] < arr[pos]) {
      pos = i;
    }
  }
  std::swap(arr[pos], arr[0]);
  std::sort(arr + 1, arr + n, compare_points);
  st[1] = 0;
  st[2] = 1;
  k = 2;
  for (int i = 2; i < n; ++i) {
    while (k >= 2 && cross_product(arr[st[k - 1]], arr[st[k]], arr[i]) > 0) {
      --k;
    }
    st[++k] = i;
  }
  std::cout << k << "\n";
  for (int i = k; i >= 1; --i) {
    std::cout << std::fixed << std::setprecision(9) << arr[st[i]].x << " " << arr[st[i]].y << "\n";
  }
  return 0;
}