Cod sursa(job #2443406)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 27 iulie 2019 19:34:14
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#define DM 120001
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;

ifstream fi ("infasuratoare.in");
ofstream fo ("infasuratoare.out");
double a, b, det;
int n, h;

class Point {
  public:
  double x, y, pos;
  void calc_Pos() {
    pos = atan2(y, x);
  };
  bool operator < (Point &other) const {
    if (pos == other.pos)
      return x > other.x || y > other.y;
    if (pos >= 0 && other.pos >= 0)
      return pos < other.pos;
    if (pos >= 0 && other.pos < 0)
      return true;
    if (pos < 0 && other.pos >= 0)
      return false;
    return pos < other.pos;
  };
  bool operator == (Point &other) const {
    return (x == other.x && y == other.y && pos == other.pos);
  };
};

vector <Point> v, sol;

int main() {
  fi >> n;
  for (int i = 0; i < n; ++i) {
    fi >> a >> b;
    v.push_back({a, b});
    v[i].calc_Pos();
  }
  sort(v.begin(), v.end());
  for (auto i:v) {
    if (i == *v.begin()) {
      sol.push_back(i);
      continue;
    }
    if (sol.size() > 1) {
      det = sol[sol.size()-2].x*sol[sol.size()-1].y + 
            sol[sol.size()-1].x*i.y +
            i.x*sol[sol.size()-2].y -
            sol[sol.size()-1].y*i.x -
            i.y*sol[sol.size()-2].x -
            sol[sol.size()-2].y*sol[sol.size()-1].x;
      while (sol.size() > 1 && det < 0) {
        sol.pop_back();
        det = sol[sol.size()-2].x*sol[sol.size()-1].y + 
              sol[sol.size()-1].x*i.y +
              i.x*sol[sol.size()-2].y -
              sol[sol.size()-1].y*i.x -
              i.y*sol[sol.size()-2].x -
              sol[sol.size()-2].y*sol[sol.size()-1].x;
      }
    }
    sol.push_back(i);
  }
  fo << sol.size() << '\n';
  for (auto i:sol)
    fo << fixed << setprecision(12) << i.x << ' ' << i.y << '\n';
  return 0;
}