Cod sursa(job #1987219)

Utilizator alexnekiNechifor Alexandru alexneki Data 29 mai 2017 23:09:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

int const nmax = 120000;

struct Point {
    double x;
    double y;

    bool operator<(Point other) const {
      if (x != other.x)
        return (x < other.x);
      else
        return (y < other.y);
    }
};

//|a.x a.y 1|
//|b.x b.y 1|
//|c.x c.y 1|
double det3(Point a, Point b, Point c) {
  double plus = a.x * b.y + a.y * c.x + b.x * c.y;
  double minus = c.x * b.y + b.x * a.y + a.x * c.y;
  return (plus - minus);
}

int n, nst;
Point p[1 + nmax];
Point st[1 + nmax];

bool compare(Point a, Point b) {
  return (det3(p[1], a, b) < 0);
}

void convexhull() {
  nst = 2;
  st[1] = p[1];
  st[2] = p[2];
  for (int i = 3; i <= n; i++) {
    while (2 < nst && (det3(st[nst - 1], st[nst], p[i]) > 0))
      nst--;
    nst++;
    st[nst] = p[i];
  }
}

int main() {
  in >> n;
  int first = 1;
  for (int i = 1; i <= n; i++) {
    in >> p[i].x >> p[i].y;
    if (p[i] < p[first])
      first = i;
  }
  swap(p[1], p[first]);
  sort(p + 1, p + n + 1, compare);
  convexhull();

  cout << nst << endl;
  while (0 < nst) {
    cout << setprecision(6) << fixed << st[nst].x << " " << st[nst].y << endl;
    nst--;
  }
  return 0;
}