Cod sursa(job #1999943)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 iulie 2017 13:40:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define MAX 25e4
using namespace std;

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

class StaculetzMagic {
public:
  StaculetzMagic() {
    this -> sz = 0;
    staculetz.resize(MAX);
  }
  int size(){
    return this -> sz;
  }
  bool empty(){
    return sz == 0;
  }
  void pop() {
    sz --;
  }
  void push(int n) {
    staculetz[++ sz] = n;
  }
  int sec() {
    return staculetz[sz - 1];
  }
  int top(){
    return staculetz[sz];
  } 
private:
  int sz; 
  vector< int > staculetz;
};

double get_sign_of_det(pair< double, double > a, pair< double, double > b, pair< double, double > c) {
  double det = (a.first * b.second) + (b.first * c.second) + (c.first * a.second) - (a.second * b.first) - (b.second * c.first) - (c.second * a.first);
  if(det == 0)
    return 0;
  if(det > 0)
    return 1;
  return -1;
}

int main() {
  cout << fixed << setprecision(6);

  int n;
  cin >> n;
  vector< pair< double, double > > v(n + 1);
  vector< bool > used(n + 1);
  StaculetzMagic *s = new StaculetzMagic();

  for(int i = 1; i <= n; i ++) {
    double x, y;
    cin >> x >> y;
    v[i] = make_pair(x, y);
  }
  sort(v.begin() + 1, v.end());
  s -> push(1);
  s -> push(2);
  used[1] = true;
  used[2] = true;

  for(int i = 3; i <= n; i ++) {
    if(get_sign_of_det(v[s -> sec()],v[s ->top()],v[i]) == -1){
      s -> push(i);
      used[i] = true; 
    }
    else {
      while(get_sign_of_det(v[s -> sec()],v[s -> top()],v[i]) != -1 and s -> size() > 1){
        used[s -> top()] =false;
        s -> pop();
      }
      used[i] = true;
      s -> push(i);
    }
  }

  vector< bool > used2(n + 1);
  int min_size = s -> size() + 1;
  s -> push(n);
  s -> push(n - 1);
  used2[n] = true;
  used2[n - 1] = true;

  for(int i = n - 2; i >= 1; i --) {
    if(get_sign_of_det(v[s -> sec()],v[s -> top()],v[i]) == -1){
      s -> push(i);
      used2[i] = true;
    }
    else {
      while(get_sign_of_det(v[s -> sec()],v[s -> top()],v[i]) != -1 and s -> size() > min_size){
        used2[s -> top()] =false;
        s -> pop();
      }
      used2[i] = true;
      s -> push(i);
    }
  }

  int sol = 0;
  for(int i = 1; i <= n; i++)
    if(used[i] or used2[i]){
      sol ++;
      used[i] = true;
    }
  cout << sol << '\n';
  while(!s -> empty()) {
    if(used[s -> top()]){
      cout << v[s -> top()].first << ' ' << v[s ->top()].second << '\n';
      used[s ->top()] = false;
    }
    s -> pop();
  }
  delete s;
}