Cod sursa(job #1999837)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 iulie 2017 11:31:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 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;

  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;
  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){
        used[s.top()] =false;
        s.pop();
      }
      used[i] = true;
      s.push(i);
    }
  }

  for(int i = 1; i <= n; i ++)
    if(used[i])
      cout << v[i].first << ' ' << v[i].second << '\n';

  vector< bool > used2(n + 1);
  stack< int > s2; 

  s2.push(n);
  s2.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[s2.top()],v[i]) == -1){
      s2.push(i);
      used2[i] = true;
    }
    else {
      while(get_sign_of_det(v[n],v[s2.top()],v[i]) != -1){
        used2[s2.top()] =false;
        s2.pop();
      }
      used2[i] = true;
      s2.push(i);
    }
  }
  for(int i = n; i >= 1; i --)
    if(used2[i] and !used[i])
      cout << v[i].first << ' ' << v[i].second << '\n';
}