Cod sursa(job #2873085)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 18 martie 2022 17:13:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair<double, double> pd;

bool shouldPop(pd a, pd b, pd c) {
  double slope1 = (b.second - a.second) / (b.first - a.first);
  double slope2 = (c.second - a.second) / (c.first - a.first);
  return slope2 > slope1;
}

int main() {
  ifstream cin("infasuratoare.in");
  ofstream cout("infasuratoare.out");
  int n;
  cin >> n;
  vector<pd> points;
  while (n--) {
    double x, y;
    cin >> x >> y;
    points.emplace_back(x, y);
  }
  cin.close();
  sort(points.begin(), points.end());
  vector<pd> ans[2];
  for (int cnt = 0; cnt < 2; ++cnt) {
    vector<pd> st;
    for (auto& i: points) {
      while (st.size() > 1 && shouldPop(st.end()[-2], st.end()[-1], i))
        st.pop_back();
      st.push_back(i);
      i.second = -i.second;
    }
    ans[cnt] = st;
  }
  reverse(ans[0].begin(), ans[0].end());
  ans[0].pop_back();
  ans[1].pop_back();
  cout << ans[0].size() + ans[1].size() << "\n";
  for (auto i: ans[0])
    cout << fixed << setprecision(12) << i.first << " " << i.second << "\n";
  for (auto i: ans[1])
    cout << fixed << setprecision(12) << i.first << " " << -i.second << "\n";
  cout.close();
  return 0;
}