Cod sursa(job #1988740)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 4 iunie 2017 15:06:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;;

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

const int 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;
  }
};

Point v[1 + nmax];
int sol[1 + nmax], nsol;

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

bool cmp(Point a, Point b) {
  return ( det3(v[0], a, b) > 0 );
}

int main() {
  int n;
  in >> n;
  for(int i = 0; i < n; ++ i) {
    in >> v[i].x >> v[i].y;
    if( v[i] < v[0] ) {
      swap(v[0], v[i]);
    }
  }

  sort(v + 1, v + n, cmp);

  nsol = 2;
  sol[1] = 0;
  sol[2] = 1;

  int i = 2;
  while(i < n) {
    if(det3(v[sol[nsol - 1]], v[sol[nsol]], v[i]) > 0) {
      sol[++nsol] = i;
      ++ i;
    } else {
      -- nsol;
    }
  }

  out << nsol << '\n';
  out << setprecision(6) << fixed;
  for(int i = 1; i <= nsol; ++ i) {
    out << v[sol[i]].x << " " << v[sol[i]].y << '\n';
  }

  return 0;
}