Cod sursa(job #3033604)

Utilizator dorufDoru Floare doruf Data 24 martie 2023 10:04:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 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 mp make_pair
#define eb emplace_back

const string TASK("infasuratoare");

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

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

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

int main() {
  fin >> n;
  int pos = 1;
  for (int i = 1; i <= n; ++i) {
    fin >> a[i].x >> a[i].y;
    if (mp(a[i].x, a[i].y) < mp(a[pos].x, a[pos].y))
      pos = i;
  }
  swap(a[1], a[pos]);
  sort(a + 2, a + n + 1, comp);
  st[1] = a[1];
  st[2] = a[2];
  int head = 2;

  for (int i = 3; i <= n; ++i) {
    while (head > 1 && cross(st[head - 1], st[head], a[i]) > 0) --head;
    st[++head] = a[i];
  }
  fout << fixed;
  fout << head << '\n';
  for (int i = 1; i <= head; ++i)
    fout << setprecision(9) << st[i].x << ' ' << st[i].y << '\n';
}