Cod sursa(job #2546305)

Utilizator nubnubMeh Neh nubnub Data 14 februarie 2020 00:23:37
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second

using namespace std;

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

typedef pair <long double, long double> pii;

int n, vf;

pii v[120005];
bool in[120005];
int st[120005];

bool orientation(pii a, pii b, pii c) {
  return (b.x - a.x) * (c.y - a.y) - (a.x - c.x) * (a.y - b.y) < 1e-12;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i].x >> v[i].y;
  sort(v + 1, v + n + 1);
  st[++vf] = 1; st[++vf] = 2;
  in[2] = 1;
  for(int i = 1, j = 1; i; i += (j = (i == n ? -j : j))) {
    if(in[i])
      continue;
    while(vf > 1 && orientation(v[st[vf - 1]], v[st[vf]], v[i]))
      in[st[vf--]] = 0;
    st[++vf] = i;
    in[st[vf]] = 1;
  }
  cout << vf - 1 << "\n" << fixed << setprecision(12);
  for(int i = 1; i < vf; i++)
    cout << v[st[i]].first << " " << v[st[i]].second << "\n";
  return 0;
}