Pagini recente » Cod sursa (job #221092) | Cod sursa (job #2056468) | Cod sursa (job #432811) | Cod sursa (job #164054) | Cod sursa (job #2069554)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
#define eps 1e-12
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
class Point {
public:
double x, y;
Point(){}
Point(double x, double y) {
this->x = x;
this->y = y;
}
bool operator< (const Point& a) const {
if (abs(this->x - a.x) < eps)
return this->y < a.y;
return this->x < a.x;
}
friend istream& operator>> (istream& in, Point& a) {
in >> a.x >> a.y;
return in;
}
friend ostream& operator<< (ostream& out, Point& a) {
out << a.x << " " << a.y;
return out;
}
};
double det(const Point& a, const Point& b, const Point& c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
vector<Point> convexHull(const vector<Point>& points) {
vector<Point> hull(points.size());
int L = -1;
for (int i = 0; i < points.size(); ++i) {
while (L > 0 && det(hull[L - 1], hull[L], points[i]) < 0)
L--;
hull[++L] = points[i];
}
int l = L;
L--;
for (int i = points.size() - 1; i >= 0; --i) {
while (L > l && det(hull[L - 1], hull[L], points[i]) < 0)
L--;
hull[++L] = points[i];
}
while (hull.size() != L)
hull.pop_back();
return hull;
}
int main() {
int N;
fin >> N;
vector<Point> points;
Point aux;
while (fin >> aux) {
points.push_back(aux);
}
sort(points.begin(), points.end());
vector<Point> chull = convexHull(points);
fout << chull.size() << "\n";
for (auto& p: chull)
fout << fixed << setprecision(7) << p << "\n";
return 0;
}