Cod sursa(job #3228342)

Utilizator RolandPetreanPetrean Roland RolandPetrean Data 7 mai 2024 17:39:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
//#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;

struct Point {
  double x, y;
  
  Point operator-(Point b) {
    return Point{x - b.x, y - b.y};
  }
  double operator^(Point b) {
    return x * b.y - y * b.x;
  }
};

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ifstream cin("infasuratoare.in");
  ofstream cout("infasuratoare.out");
  
  int n;
  cin >> n;
  
  vector<Point> p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i].x >> p[i].y;
  }
  
  for (int i = 1; i < n; ++i) {
    if (p[i].y < p[0].y) {
      swap(p[i], p[0]);
    }
  }
  sort(p.begin() + 1, p.end(), [&](Point a, Point b) {
    return ((a - p[0]) ^ (b - p[0])) > 0;
  });
  
  vector<int> st;
  for (int i = 0; i < n; ++i) {
    if (st.empty()) {
      st.push_back(i);
      continue;
    }
    
    int a = st.back();
    st.pop_back();
    
    while (!st.empty() && ((p[st.back()] - p[a]) ^ (p[i] - p[a])) > 0) {
      a = st.back();
      st.pop_back();
    }
    
    st.push_back(a);
    st.push_back(i);
  }
  
  reverse(st.begin(), st.end());
  cout << st.size() << endl;
  for (int i : st) {
    cout << fixed << p[i].x << " " << p[i].y << endl;
  }
}