Cod sursa(job #2574944)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 6 martie 2020 10:48:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 2e5 + 5;

struct Point {
  long double x, y;
};

int n, k;

Point v[MAX_N];

int st[MAX_N];

long double f(Point a, Point b, Point c) {
  return (a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y);
}

bool operator < (const Point &a, const Point &b) {
  return (a.x < b.x || (a.x == b.x && a.y < b.y));
}

bool compare (const Point &a, const Point &b) {
  return (f(v[0], a, b) < 0);
}

int main() {
  int p;
  fin >> n;
  for (int i = 0; i < n; ++i) {
    fin >> v[i].x >> v[i].y;
  }
  p = 0;
  for (int i = 1; i < n; ++i) {
    if (v[i] < v[p]) {
      p = i;
    }
  }
  swap(v[0], v[p]);
  sort(v + 1, v + n, compare);
  st[1] = 0;
  st[2] = 1;
  k = 2;
  for (int i = 2; i < n; ++i) {
    while (k > 1 && f(v[st[k - 1]], v[st[k]], v[i]) > 0) {
      --k;
    }
    st[++k] = i;
  }
  fout << k << "\n";
  for (int i = k; i > 0; --i) {
    fout << fixed << setprecision(13) << v[st[i]].x << " " << v[st[i]].y << "\n";
  }
  return 0;
}