Cod sursa(job #1999910)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 iulie 2017 12:58:29
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 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< 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);

  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;

  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; 
    }
    else {
      while(get_sign_of_det(v[1],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[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 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();
  }

}