Pagini recente » Cod sursa (job #619579) | Cod sursa (job #1002788) | Cod sursa (job #21527) | Cod sursa (job #166109) | Cod sursa (job #472123)
Cod sursa(job #472123)
#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;
}