Cod sursa(job #3139028)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 24 iunie 2023 13:25:01
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

double const INF = 1e9+7;

struct Point {
  double x, y;
};

Point origin;

int const NMAX = 1200000;
Point field[1 + NMAX];

bool compareAngle(Point a, Point b) {
  if(a.x == origin.x && a.y == origin.y) {
    return true;
  }else if(b.x == origin.x && b.y == origin.y) {
    return false;
  }else {
    if((a.y < origin.y && b.y < origin.y) || (origin.y < a.y && origin.y < b.y)) {
      return ((a.y - origin.y) * (b.x - origin.x)) < ((b.y - origin.y) * (a.x - origin.x));
    }else {
      return (a.y < b.y);
    }
  }
}

double computeDeterminant(Point a, Point b, Point c) {
  //cerr << a.x << ' ' << a.y << ", " << b.x << ' ' << b.y << ", " << c.x << ' ' << c.y << ": " << ((a.x * b.y) + (b.x * c.y) + (c.x * a.y)) - ((b.x * a.y) + (c.x * b.y) + (a.x * c.y)) << '\n';
  return ((a.x * b.y) + (b.x * c.y) + (c.x * a.y)) - ((b.x * a.y) + (c.x * b.y) + (a.x * c.y));
}

int main() {

  int n;
  in >> n;
  origin.x = INF;
  origin.y = INF;
  for(int i = 1;i <= n;i++) {
    in >> field[i].x >> field[i].y;
    if(field[i].x < origin.x) {
      origin.x = field[i].x;
      origin.y = field[i].y;
    }else if(field[i].x == origin.x){
      origin.y = min(field[i].y, origin.y);
    }
  }
  sort(field+1, field+n+1, compareAngle);
  vector <Point> st;
  //cerr << origin.x << ' ' << origin.y << '\n';
  for(int i = 1;i <= n;i++) {
    while(st.size() > 1 && (computeDeterminant(st[st.size() - 2], st[st.size() - 1], field[i]) < 0.0)) {
      st.pop_back();
    }
    st.push_back(field[i]);
  }
  out << st.size() << '\n';
  for(int i = 0;i < st.size();i++) {
    out << st[i].x << ' ' << st[i].y << '\n';
  }
  return 0;
}