Cod sursa(job #2605771)

Utilizator avtobusAvtobus avtobus Data 25 aprilie 2020 19:25:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pt;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-12;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

inline bool cmp3(const pt &O, const pt &A, const pt &B) {
  return (A.second - O.second) * (B.first - O.first) < (B.second - O.second) * (A.first - O.first) + EPS;
}

int main(void) {
  // freopen("infasuratoare.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  int N;
  fin >> N;
  vector<pt> pts(N);
  rep(i, N) {
    fin >> pts[i].first >> pts[i].second;
  }

  auto cmpY = [](pt A, pt B) {
    return (A.second < B.second) || (A.second == B.second && A.first < B.first);
  };

  pt &origin  = *min_element(pts.begin(), pts.end(), cmpY);

  swap(origin, pts.front());

  auto cmpAngle = [&O=pts.front()](pt A, pt B) {
    return cmp3(O, A, B);
  };
  sort(pts.begin()+1, pts.end(), cmpAngle);

  stack<pt> st;
  st.push(pts[0]);
  st.push(pts[1]);

  for(int i = 2; i < N; ++i) {
    pt z = pts[i];
    while(st.size() > 1) {
      pt y = st.top(); st.pop();
      pt x = st.top();
      if (!cmp3(y, x, z)) {
        st.push(y);
        break;
      }
    }
    st.push(z);
  }
  fout << st.size() << endl;
  fout << setprecision(6) << fixed;
  vector<pt> hull(st.size());
  int i = st.size();
  while(!st.empty()) {
    hull[--i] = st.top();
    st.pop();
  }
  for(auto X: hull) {
    fout << X.first << " " << X.second << '\n';
  }
  fout << endl;

  return 0;
}