Cod sursa(job #1999857)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 iulie 2017 12:05:50
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

double get_sign_of_det(pair< long long, long long > a, pair< long long, long long > b, pair< long long, long long > c) {
  long long 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;
  int sol = 0;
  vector< pair< double, double > > v(n + 1);
  vector< bool > used(n + 1, false);
  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());

  stack< int > s;

  s.push(1);
  s.push(2);
  used[1] = true;
  used[2] = true;
  int st_elem = 2;
  for(int i = 3; i <= n; i ++) {
    if(get_sign_of_det(v[1],v[s.top()],v[i]) == -1){
      s.push(i);
      used[i] = true;
      st_elem ++;
    }
    else {

      while(get_sign_of_det(v[1],v[s.top()],v[i]) != -1){
        used[s.top()] =false;
        s.pop();
      }
      used[i] = true;
      s.push(i);
    }
  }

  vector< bool > used2(n + 1);
  s.push(n);
  s.push(n - 1);
  used2[n - 1] = true;
  for(int i = n - 2; i >= 1; i --) {
    if(get_sign_of_det(v[n],v[s.top()],v[i]) == -1){
      s.push(i);
      used2[i] = true;
    }
    else {
      while(get_sign_of_det(v[n],v[s.top()],v[i]) != -1){
        used2[s.top()] =false;
        s.pop();
      }
      used2[i] = true;
      s.push(i);
    }
  }
  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();
  }
}