Cod sursa(job #3205913)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 20 februarie 2024 22:38:12
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3 kb
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#ifndef DLOCAL
  #define cin fin
  #define cout fout
  ifstream cin("infasuratoare.in");
  ofstream cout("infasuratoare.out");
#endif

//#define int ll
#define double ld
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

struct Circle {
  ld x, y;
  ld r;
};

struct Point {
  ld x, y;
};

Point eclipse(Circle a, Circle b) {
  if(a.r < b.r) swap(a, b);
  Point vec = Point{b.x - a.x, b.y - a.y};
  
  vec.x /= (a.r - b.r);
  vec.y /= (a.r - b.r);
  
  return Point{b.x + vec.x * b.r, b.y + vec.y * b.r};
}

double dist(Point a, Point b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

const double eps = 1e-12;

vector<Point> convex_hull(vector<Point> v) {
  sort(all(v), [&](auto a, auto b) { return a.x < b.x || (a.x == b.x && a.y > a.y); });
  vector<Point> upper, lower;
  
  Point L = v[0], R = v.back();
  
  auto orient = [&](Point O, Point A, Point B) { // A la stanga lui B ==> +
    auto a = A.x - O.x, b = A.y - O.y, c = B.x - O.x, d = B.y - O.y;
    return a * d - c * b > eps? +1 : a * d - c * b < eps? -1 : 0;
  };
  
  upper.emplace_back(L);
  lower.emplace_back(L);
  for(auto x : v | views::drop(1) | views::take(sz(v) - 2)) {
    if(orient(L, x, R) == +1)
      lower.emplace_back(x);
    else
      upper.emplace_back(x);
  }
  
  
  lower.emplace_back(R);
  upper.emplace_back(R);
  
  auto mkst = [&orient](vector<Point> lst) {
    vector<Point> st;
    st.emplace_back(lst[0]);
    for(auto x : lst | views::drop(1)) {
      while(sz(st) >= 2 && orient(rbegin(st)[1], rbegin(st)[0], x) >= 0)  st.pop_back();
      st.emplace_back(x);
    }
    st.pop_back();
    return st;
  };
  
  auto pesus = mkst(upper);
  
  //for(auto [a, b] : pesus) cerr << a << ' ' << b << '\t'; cerr << '\n';
  
  reverse(all(lower));
  auto pejos = mkst(lower);
  
  //for(auto [a, b] : pejos) cerr << a << ' ' << b << '\t'; cerr << '\n';
  
  copy(all(pejos), back_inserter(pesus));
  
  return pesus;
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n;
  cin >> n;
  
  //vector<Circle> circ(n);
  //for(auto &[x, y, r] : circ) {
    //cin >> x >> y >> r;
  //}
  //sort(all(circ), [&](auto a, auto b) { return a.r < b.r; });
  
  vector<Point> rez(n);
  for(auto &[a, b] : rez) cin >> a >> b;
  //for(int i = 1; i < sz(circ); i++)
    //rez.emplace_back(eclipse(circ[i], circ[i - 1]));

  auto cvhull = convex_hull(rez);
  
  //cerr << "--\n";
  
  //for(auto [a, b] : cvhull) cerr << a << ' ' << b << '\n';
  
  //cerr << "--\n";
  
  //double sum = 0;
  
  reverse(all(cvhull));
  //for(int i = 0; i < sz(cvhull); i++)
    //sum += dist(cvhull[i], cvhull[(i - 1 + sz(cvhull)) % sz(cvhull)]);
  
  cout << sz(cvhull) << '\n';
  //cerr << "--\n";
  for(auto [x, y] : cvhull) cout << setprecision(12) << fixed << x << ' ' << y << '\n';
  
  //cout << setprecision(18) << fixed << sum << '\n';
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/