Cod sursa(job #2990974)

Utilizator raresgherasaRares Gherasa raresgherasa Data 8 martie 2023 20:34:42
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 120005;

struct Points{
   double x, y;
};

Points v[N_MAX];
int n;
int stk[N_MAX];

double solve (Points a, Points b, Points c){
   return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool sort_unghi (Points a, Points b){
   return solve(v[1], a, b) < 0;
}

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n;
   for (int i = 1; i <= n; i++){
      fin >> v[i].x >> v[i].y;
   }

   int pos = 1;
   for (int i = 2; i <= n; i++){
      if (make_pair(v[i].x, v[i].y) < make_pair(v[pos].x, v[pos].y)){
         pos = i;
      }
   }

   swap(v[1], v[pos]);
   sort(v + 2, v + n + 1, sort_unghi);
   stk[++stk[0]] = 1;
   stk[++stk[0]] = 2;
   for (int i = 3; i <= n; i++){
      while (stk[0] >= 2 && solve(v[stk[stk[0] - 1]], v[stk[stk[0]]], v[i]) > 0){
         --stk[0];
      }
      stk[++stk[0]] = i;
   }

   fout << stk[0] << '\n';
   for (int i = 1; i <= stk[0]; i++){
      fout << fixed << setprecision(9) << v[stk[i]].x << " " << v[stk[i]].y << '\n';
   }
}