Pagini recente » Cod sursa (job #2010737) | Cod sursa (job #3190749) | Cod sursa (job #11360) | Statistici ASEM-Lozovanu-Marina (rynalozovanu) | Cod sursa (job #2587557)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class Point{
public:
Point(double x, double y):x_(x), y_(y) {}
bool operator < (const Point& other) const {
if (x() == other.x())
return y() < other.y();
return x() < other.x();
}
double x() const {return x_;}
double y() const {return y_;}
private:
double x_, y_;
};
/**
| a.x a.y 1| | a.x a.y 1|
| b.x b.y 1| =| b.x - a.x b.y - a.y 0| = (b.x - a.x)*(c.y-a.y) - (c.x - a.x)*(b.y - a.y)
| c.x c.y 1| | c.x - a.x c.y - a.y 0|
*/
double det(Point a, Point b, Point c)
{
return (b.x() - a.x())*(c.y()-a.y()) - (c.x() - a.x())*(b.y() - a.y());
}
vector<Point> points;
void convexHull()
{
sort(points.begin(), points.end());
Point pmin = points.front();
Point pmax = points.back();
vector<Point> upper_envelope, lower_envelope;
for (vector<Point>::iterator it = points.begin(); it != points.end(); ++it) {
Point p = *it;
if (det(pmin, pmax, p) >= 0) {
while (upper_envelope.size() >= 2 &&
det(upper_envelope[(int)upper_envelope.size() - 2],
upper_envelope[(int)upper_envelope.size() - 1],
p) > 0)
upper_envelope.pop_back();
upper_envelope.emplace_back(p);
}
}
for (vector<Point>::reverse_iterator it = points.rbegin(); it != points.rend(); ++it) {
Point p = *it;
if (det(pmax, pmin, p) >= 0) {
while (lower_envelope.size() >= 2 &&
det(lower_envelope[(int)lower_envelope.size() - 2],
lower_envelope[(int)lower_envelope.size() - 1],
p) > 0)
lower_envelope.pop_back();
lower_envelope.emplace_back(p);
}
}
printf("%d\n", (int)lower_envelope.size() + (int)upper_envelope.size() - 2);
for (int i = 0; i < upper_envelope.size(); ++i)
printf("%lf %lf\n", upper_envelope[i].x(), upper_envelope[i].y());
for (int i = (int)lower_envelope.size() - 2; i > 0; --i)
printf("%lf %lf\n", lower_envelope[i].x(), lower_envelope[i].y());
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N;
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
double x, y;
scanf("%lf%lf", &x, &y);
points.emplace_back(x,y);
}
convexHull();
return 0;
}