Cod sursa(job #2978012)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 12 februarie 2023 19:27:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define double long double

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

vector< pair <double, double>> v, hull;

vector< pair< double, double>> convex_hull(vector< pair< double, double>>);
int convex(pair<double, double>, pair<double, double>, pair<double, double>);

int main()
{
  int i, n;
  double a, b;
  fin>>n;
  for(i=1; i<=n; i++)
  {
    fin>>a>>b;
    v.push_back(make_pair(a, b));
  }
  hull=convex_hull(v);
  fout<<hull.size()<<'\n';
  for(auto i:hull) fout<<fixed<<setprecision(12)<<i.first<<' '<<i.second<<'\n';
}

int convex(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
   return (a.first-c.first)*(b.second-c.second)-(a.second-c.second)*(b.first-c.first);
}

vector< pair< double, double>> convex_hull(vector< pair< double, double>> v)
{
  pair< double, double> p1, p2;
  vector< pair< double, double>> hull;
  hull.clear();
  sort(v.begin(), v.end());
  for(auto i:v)
  {
    while(hull.size()>=2)
    {
      p1=hull[hull.size()-2];
      p2=hull[hull.size()-1];
      if(convex(p2, i, p1)<=0) break;
      hull.pop_back();
    }
    hull.push_back(i);
  }
  hull.pop_back();
  reverse(v.begin(), v.end());
  for(auto i:v)
  {
    while(hull.size()>=2)
    {
      p1=hull[hull.size()-2];
      p2=hull[hull.size()-1];
      if(convex(p2, i, p1)<=0) break;
      hull.pop_back();
    }
    hull.push_back(i);
  }
  hull.pop_back();
  return hull;
}