Cod sursa(job #1999979)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 iulie 2017 14:27:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 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];
  } 
  vector< int > staculetz;
private:
  int sz; 
  
};

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);

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

  for(int i = 1; i <= n; i ++) {
    cin >> v[i].first >> v[i].second;
  }
  sort(v.begin() + 1, v.end());

  int sol = 1;
  s -> push(1);
  s -> push(2);
  used[2] = true;

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

  int min_size = s -> size();

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

  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;
}