Cod sursa(job #2936202)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 8 noiembrie 2022 11:51:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct {
  double x, y;
  int ind;
  punct(double x, double y, int ind) {
    this->x = x; 
    this->y = y;
    this->ind = ind;
  }
  bool operator<(const punct &other) {
    if (x != other.x)
      return x < other.x;
    return y < other.y;
  }
  void show() { out << fixed << setprecision(6) << x << ' ' << y << '\n'; }
};

bool eval(const punct &a, const punct &b, const punct &c) {
  return (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y) <= 0;
}

vector<punct> infasuratoare(vector<punct> puncte) {
  sort(puncte.begin(), puncte.end());
  vector<punct> res;
  for (int i = 0; i < puncte.size(); i++) {
    while (res.size() >= 2 &&
           eval(res[res.size() - 2], res[res.size() - 1], puncte[i])) {
      res.pop_back();
    }
    res.push_back(puncte[i]);
  }
  int tmp = res.size() + 1;

  for (int i = puncte.size() - 2; i >= 0; i--) {
    while (res.size() >= tmp &&
           eval(res[res.size() - 2], res[res.size() - 1], puncte[i])) {
      res.pop_back();
    }
    res.push_back(puncte[i]);
  }
  return res;
}

int main() {
  vector<punct> puncte;
  int n;
  in >> n;
  for (int i = 0; i < n; i++) {
    double x, y;
    in >> x >> y;
    puncte.push_back(punct(x, y, 0));
  }
  vector<punct> res = infasuratoare(puncte);
  out << res.size() - 1 << '\n';
  for (int i = 1; i < res.size(); i++)
    res[i].show();
}