Pagini recente » Cod sursa (job #3032450) | Cod sursa (job #2605924) | Cod sursa (job #2855034) | Cod sursa (job #456547) | Cod sursa (job #471801)
Cod sursa(job #471801)
#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;
}