Cod sursa(job #471801)

Utilizator marius.pungaruMarius Pungaru marius.pungaru Data 21 iulie 2010 00:32:58
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <algorithm>
#include <complex>
#include <cstdio>
#include <vector>

using namespace std;

#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"
#define EPS 1e-12

bool points_compare(complex<double> a, complex<double> b) {
  if (abs(imag(a) - imag(b)) < EPS) {
    return real(a) < real(b);
  }
  return imag(a) < imag(b);
}

bool right_rotation(vector<complex<double> > hull,
                    complex<double> point) {
  if (hull.size() < 2) {
    return false;
  }

  complex<double> a = hull[hull.size() - 2], b = hull.back(), c = point;
  b = b - a;
  b = conj(b / abs(b));
  c = c - a;
  return imag(c * b) < -EPS; 
}

void convex_hull(vector<complex<double> > points,
                 vector<complex<double> > &hull) {
  if (points.size() < 4) {
    for (vector<complex<double> >::iterator it = points.begin();
         it != points.end();
         ++it) {
      hull.push_back(*it);
    }
    return;
  }

  sort(points.begin(), points.end(), points_compare);

  vector<complex<double> >::iterator it = points.begin();

  hull.push_back(*(it++));
  hull.push_back(*(it++));

  for (; it != points.end(); ++it) {
    for (; right_rotation(hull, *it); hull.pop_back()) ;
    hull.push_back(*it);
  }

  for (--it, --it; it != points.begin(); --it) {
    for (; right_rotation(hull, *it); hull.pop_back()) ;
    hull.push_back(*it);
  }

  for (; right_rotation(hull, points[0]); hull.pop_back()) ;
}

int main(void) {
  int num_points;
  vector<complex<double> > points, hull;

  freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);

  scanf("%d", &num_points);
  for (int i = 0; i < num_points; ++i) {
    double x, y;
    scanf("%lf%lf", &x, &y);
    points.push_back(complex<double>(x, y));
  }

  convex_hull(points, hull);

  printf("%d\n", hull.size());
  for (vector<complex<double> >::iterator it = hull.begin();
       it != hull.end();
       ++it) {
    printf("%lf %lf\n", real(*it), imag(*it));
  }
  
  return 0;
}