Pagini recente » Cod sursa (job #2413660) | Cod sursa (job #2187145) | Cod sursa (job #2816490) | Cod sursa (job #2794749) | Cod sursa (job #3138941)
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "infasuratoare";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
constexpr int PREC = 12;
struct Point {
double x, y;
Point() { x = y = 0; }
Point(double x, double y): x(x), y(y) {}
static double crossProd(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
static double crossProd(const Point &a, const Point &b, const Point &c) {
return crossProd(b - a, c - a);
}
bool operator <(const Point &other) const noexcept {
return (y < other.y || (y == other.y && x < other.x));
}
bool operator ==(const Point &other) const noexcept {
return x == other.x && y == other.y;
}
Point operator -(const Point &other) const noexcept {
return Point(x - other.x, y - other.y);
}
Point &operator =(const Point &other) {
this->x = other.x;
this->y = other.y;
return *this;
}
};
class GrahamScanner {
public:
GrahamScanner(const vector<Point> &points): points(points) {
init();
}
vector<Point> scan() {
vector<Point> ans = { points[0], points[1] };
for (size_t i = 2; i < points.size(); i++) {
while (ans.size() >= 2 && Point::crossProd(ans[ans.size() - 2], ans.back(), points[i]) < 0) {
ans.pop_back();
}
ans.push_back(points[i]);
}
return ans;
}
private:
vector<Point> points;
void init() {
placeSentinel();
sort(points.begin() + 1, points.end(), GrahamScanner::PolarCmp(points[0]));
}
void placeSentinel() {
vector<Point>::iterator sentinel = points.end();
for (auto it = points.begin(); it != points.end(); it++) {
if (*it < *sentinel) {
sentinel = it;
}
}
iter_swap(points.begin(), sentinel);
}
struct PolarCmp {
Point origin;
PolarCmp(const Point &origin): origin(origin) {}
bool operator ()(const Point &a, const Point &b) {
return Point::crossProd(origin, a, b) > 0;
}
};
};
int main() {
int n;
fin >> n;
vector<Point> points(n);
for (auto &point : points) {
fin >> point.x >> point.y;
}
GrahamScanner gScanner(points);
auto hull = gScanner.scan();
fout << hull.size() << '\n';
for (const auto &point : hull) {
fout << fixed << setprecision(PREC) << point.x << ' ' << point.y << '\n';
}
return 0;
}