Cod sursa(job #2103747)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 10 ianuarie 2018 19:25:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

struct Point {
  double x, y;
};

inline int Det (Point a, Point b, Point c) {
  
  double d = (a.x * b.y) + (b.x * c.y) + (c.x * a.y) - (a.y * b.x) - (b.y * c.x) - (c.y * a.x);
  
  if (d < 0.0) {
    return -1;
  }
  
  if (d > 0.0) {
    return 1;
  }

  return 0;
}

int main () {
  
  freopen ("infasuratoare.in", "r", stdin);
  freopen ("infasuratoare.out", "w", stdout);
  //MODIFICA FISIERELE

  ios::sync_with_stdio (false);
  cout << fixed << setprecision(12);

  int n; 
  cin >> n;

  vector < Point > v (n + 1);
  for (int i = 1; i <= n; ++ i) {
    cin >> v[i].x >> v[i].y;
  }
  
  sort (v.begin() + 1, v.end(), [] (Point a, Point b) -> bool {
      if (a.x < b.x) {
        return true;
      }
      if (a.x == b.x and a.y < b.y) {
        return true;
      }
      return false;
    });
  
  vector < bool > used(n + 1);
  vector < int > stk (2 * n + 2);
 
  int peak = 0;
  for (int i = 1; i <= n; ++ i) {
    while (peak > 1 and Det(v[stk[peak - 1]], v[stk[peak]], v[i]) >= 0) {
      -- peak;
    }

    stk[++ peak] = i;
  }
  
  int last = peak;
  for (int i = n; i >= 1; -- i) {
    while (peak > last and Det(v[stk[peak - 1]], v[stk[peak]], v[i]) >= 0) {
      -- peak;
    }
    stk[++ peak] = i;
  }
  
  for (int i = peak; i >= 1; -- i) {
    if (used[i]) {
      continue;
    }

    used[i] = true;
    cout << v[stk[i]].x << ' ' << v[stk[i]].y << '\n';
  }
}