Cod sursa(job #2914157)

Utilizator avtobusAvtobus avtobus Data 19 iulie 2022 08:10:10
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iterator>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ld, ld> pld;
typedef complex<ld> C;

int main(void) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  // freopen("infasuratoare.in", "r", stdin);
  // freopen("infasuratoare.out", "w", stdout);
  int N;
  cin >> N;
  vector<C> P(N);
  for(int i = 0; i < N; i++) {
    ld x,y;
    cin >> x >> y;
    P[i] = {x,y};
  }
  sort(P.begin(), P.end(), [](const C &A, const C &B) {
    return A.real() < B.real() || (A.real() == B.real() && A.imag() < B.imag());
  });
  auto is_counter_clockwise = [](const C &X, const C &Y, const C &Z)->bool {
    return (conj(Y-X) * (Z-Y)).imag() > 0;
  };
  vector<C> hull;
  int cnt;
  vector<C> st(N+1);
  {
    cnt = 0;
    st[cnt++] = P.front();
    for(int i = 1; i < N; i++) {
      auto Z = P[i];
      while(cnt >= 2) {
        auto X = st[cnt-2];
        auto Y = st[cnt-1];
        if (!is_counter_clockwise(X, Y, Z)) {
          cnt--;
        } else break;
      }
      st[cnt++] = Z;
    }
    copy(st.begin(), st.begin() + cnt-1, std::back_inserter(hull));
  }
  {
    cnt = 0;
    st[cnt++] = P.back();
    for(int i = N-2; i >= 0; i--) {
      auto Z = P[i];
      while(cnt >= 2) {
        auto X = st[cnt-2];
        auto Y = st[cnt-1];
        if (!is_counter_clockwise(X, Y, Z)) {
          cnt--;
        } else break;
      }
      st[cnt++] = Z;
    }
    copy(st.begin(), st.begin() + cnt-1, std::back_inserter(hull));
  }
  cout << hull.size() << "\n";
  for(auto c: hull) {
    cout << fixed << setprecision(6) << c.real() << " " << c.imag() << "\n";
  }

  return 0;
}