Cod sursa(job #2304896)

Utilizator lucametehauDart Monkey lucametehau Data 18 decembrie 2018 19:34:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <bitset>

using namespace std;

// cine se crede smecher sa bage "Convex Hull Trick" :)

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

typedef pair <long double, long double> Point;

int n, vf;
bool ok;

int st[120005];
Point v[120005];
bitset <120005> viz;

bool Check(Point C, Point A, Point B) {
  return ((A.first - C.first) * (B.second - C.second) - (A.second - C.second) * (B.first - C.first) < 1e-12);
}

void Add(int &i) {
  i += (ok ? 1 : -1);
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i].first >> v[i].second;
  sort(v + 1, v + n + 1);
  st[1] = 1; st[2] = 2; vf = 2;
  viz[2] = ok = 1;
  int i = 1;
  while(i) {
    if(viz[i]) {
      Add(i);
      continue;
    }
    while(vf > 1 && Check(v[st[vf - 1]], v[st[vf]], v[i]))
      viz[st[vf--]] = 0;
    st[++vf] = i;
    viz[i] = 1;
    if(i == n)
      ok = 0;
    Add(i);
  }
  cout << vf - 1 << "\n";
  cout << fixed << setprecision(12);
  for(int i = 1; i < vf; i++)
    cout << v[st[i]].first << " " << v[st[i]].second << "\n";
  return 0;
}