Cod sursa(job #3041349)

Utilizator dorufDoru Floare doruf Data 31 martie 2023 12:39:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int,int>;
#define eb emplace_back

const string TASK("infasuratoare");

ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");

const int N = 120000 + 5;
struct Point {ld x, y;} v[N];

ld prod(Point& o, Point& a, Point& b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool cmp(Point& a, Point& b) {
  return prod(v[1], a, b) < 0;
}

int n, head;
Point hull[N];

int32_t main() {
  fin >> n;
  int pos = 1;
  for (int i = 1; i <= n; ++i) {
    fin >> v[i].x >> v[i].y;
    if (make_pair(v[i].x,v[i].y) < make_pair(v[pos].x,v[pos].y))
      pos = i;
  }
  swap(v[1], v[pos]);
  sort(v + 2, v + n + 1, cmp);
  hull[1] = v[1];
  hull[2] = v[2];
  head = 2;
  for (int i = 3; i <= n; ++i) {
    while (head >= 2 && prod(hull[head-1], hull[head], v[i]) > 0)
      --head;
    hull[++head] = v[i];
  }
  fout << fixed;
  fout << head << '\n';
  for (int i = head; i > 0; --i)
    fout << setprecision(9) << hull[i].x << ' ' << hull[i].y << '\n';
}