Cod sursa(job #2691781)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 29 decembrie 2020 23:31:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

const int NMAX = 120000;

const double EPS = 1e-12;

struct Punct
{
  double x;
  double y;

  bool operator <(const Punct& other) const
  {
    if (this->x == other.x)
      return this->y < other.y;
    return this->x < other.x;
  }
};

Punct punct[1 + NMAX];

int vf;
int stiva[1 + NMAX];

bool vizitat[1 + NMAX];

double ccw(const Punct& o, const Punct& a, const Punct& b)
{
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

int main()
{
  ifstream in("infasuratoare.in");
  ofstream out("infasuratoare.out");
  int n;

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

  sort(punct + 1, punct + 1 + n);

  vf++;
  stiva[vf] = 1;

  for (int i = 2, pas = 1; i > 0; i += pas)
  {
    if (vizitat[i]) continue;

    while (vf > 1 && ccw(punct[stiva[vf - 1]], punct[stiva[vf]], punct[i]) < EPS)
    {
      vizitat[stiva[vf]] = false;
      vf--;
    }

    vf++;
    stiva[vf] = i;
    vizitat[i] = true;

    if (i == n)
      pas = -1;

    //for (int j = 1; j <= vf; ++j)
    //  out << punct[stiva[j]].x << ' ' << punct[stiva[j]].y << ", ";
    //out << '\n';
  }

  out << vf - 1 << '\n' << fixed << setprecision(6);
  for (int i = 1; i < vf; i++)
  {
    out << punct[stiva[i]].x << ' ' << punct[stiva[i]].y << '\n';
  }

  return 0;
}