Cod sursa(job #2461476)

Utilizator AlexNeaguAlexandru AlexNeagu Data 25 septembrie 2019 19:01:48
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.in");
typedef pair < double, double > pi;
int n;
pi v[105];
inline double cp(const pi& a, const pi& b, const pi& c) {
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline double cmp(const pi &p1, const pi &p2) {
   return cp(v[1], p1, p2) < 0;
}
void graham() {
  pi st[105];
  st[1] = v[1];
  st[2] = v[2];
  int h = 2;
  for (int i = 3; i <= n; i++) {
    while(h >= 2 && cp(st[h - 1], st[h], v[i]) > 0) --h;
    st[++h] = v[i];
  }
  cout << h << "\n";
  for (int i = h; i >= 1; i--) cout << fixed << setprecision(9) << st[i].x << " " << st[i].y << "\n";
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v[i].x >> v[i].y;
  }
  int ind = 1;
  for (int i = 2; i <= n; i++) if (v[i] < v[ind]) ind = i;
  swap(v[1], v[ind]);
  sort(v + 2, v + n + 1, cmp);
  graham();
}