Cod sursa(job #2914162)

Utilizator avtobusAvtobus avtobus Data 19 iulie 2022 08:38:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <algorithm>
#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;
  };
  {
    auto mid = stable_partition(P.begin()+1, P.begin()+N-1, [&](const C &X) {
      return is_counter_clockwise(P.front(), X, P.back());
    });
    reverse(mid, P.end());
  }
  P.push_back(P.front()); N++;

  int cnt = 0;
  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;
  }
  cout << cnt - 1 << "\n";
  for(int i = 0; i < cnt-1; i++) {
    auto c = st[i];
    cout << fixed << setprecision(6) << c.real() << " " << c.imag() << "\n";
  }


  return 0;
}