Cod sursa(job #472123)

Utilizator marius.pungaruMarius Pungaru marius.pungaru Data 22 iulie 2010 23:32:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 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(const complex<double> &a, const complex<double> &b) {
  if (abs(imag(a) - imag(b)) < EPS) {
    return real(a) < real(b);
  }
  return imag(a) < imag(b);
}

bool right_rotation(const vector<complex<double> > &hull,
                    const 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) {
  vector<complex<double> >::iterator it;
  vector<complex<double> >::reverse_iterator rit;

  if (points.size() < 4) {
    for (it = points.begin(); it != points.end(); ++it) {
      hull.push_back(*it);
    }
    return;
  }

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

  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 (rit = points.rbegin(), ++rit; rit != points.rend(); ++rit) {
    for (; right_rotation(hull, *rit); hull.pop_back()) ;
    hull.push_back(*rit);
  }

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