Cod sursa(job #3216126)

Utilizator dorufDoru Floare doruf Data 15 martie 2024 17:35:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define eb emplace_back
using ll = long long;
using ld = long double;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int N = 125000 + 5;
const int Inf = 1e9;
struct P {
  ld x, y;
  bool operator < (const P& oth) const {
    return make_pair(x,y) < make_pair(oth.x,oth.y);
  }
};

P p[N];
int n, o, k;
P hull[N];

ld cross(P o, P a, P b) {
  return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
bool cmp(P a, P b) {
  return cross(p[1],a,b) < 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  fin.tie(0);
  fout.tie(0);
  fin >> n;
  for (int i = 1; i <= n; ++i) {
    fin >> p[i].x >> p[i].y;
    if (!o || p[i] < p[o]) o = i;
  }
  swap(p[1],p[o]);
  sort(p + 2, p + n + 1, cmp);
  hull[1] = p[1];
  hull[2] = p[2];
  k=2;
  for (int i = 3; i <= n; ++i) {
    while (k >= 2 && cross(hull[k-1],hull[k],p[i])>0) --k;
    hull[++k]=p[i];
  }
  fout << k << '\n';
  fout << fixed << setprecision(12);
  for (int i = k; i > 0; --i)
    fout << hull[i].x << ' ' << hull[i].y << '\n';
}