Pagini recente » Cod sursa (job #243298) | Cod sursa (job #268948) | Cod sursa (job #2838370) | Cod sursa (job #2500329) | Cod sursa (job #1812164)
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
class ConvexHullGraham {
public:
struct Point {
double x_;
double y_;
Point* sentinel_;
Point() : x_(0.0), y_(0.0), sentinel_(nullptr) {};
Point(double x, double y) : x_(x), y_(y), sentinel_(nullptr) {};
Point(double x, double y, Point* sentinel) : x_(x), y_(y), sentinel_(sentinel) {};
Point& operator =(const Point& other) {
this->x_ = other.x_;
this->y_ = other.y_;
return *this;
}
Point& operator =(const pair<double, double>& other) {
this->x_ = other.first;
this->y_ = other.second;
return *this;
}
};
ConvexHullGraham(const vector<pair<double, double>>& input_points) {
int sentinel_index = 0;
pair<double, double> sentinel = input_points[0];
int current_index = 0;
for (auto& point : input_points) {
if (point < sentinel) {
sentinel = point;
sentinel_index = current_index;
}
current_index++;
}
Point* sentinel_pointer = new Point(sentinel.first, sentinel.second);
for (auto& point : input_points) {
points_.emplace_back(point.first, point.second, sentinel_pointer);
}
swap(points_[0], points_[sentinel_index]);
}
vector<pair<double, double>> GetConvexHull() {
sort(points_.begin() + 1, points_.end(), PolarComparator);
vector<Point> stack;
for (auto& point : points_) {
int size = stack.size();
while (size >= 2
&& CrossProduct(stack[size - 2], stack[size - 1], point) < 0) {
stack.pop_back();
size--;
}
stack.push_back(point);
}
vector<pair<double, double>> convex_hull;
for (auto& point : stack) {
convex_hull.emplace_back(point.x_, point.y_);
}
return convex_hull;
}
private:
vector<Point> points_;
Point sentinel_;
static double CrossProduct(const Point& a, const Point& b, const Point& c) {
return (b.x_ - a.x_) * (c.y_ - a.y_) - (c.x_ - a.x_) * (b.y_ - a.y_);
}
static bool PolarComparator (const Point& a, const Point& b) {
return CrossProduct(*a.sentinel_, a, b) > 0;
}
};
int main() {
cin.sync_with_stdio(false);
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
vector<pair<double, double>> points_;
for (int i = 0; i < n; i++) {
double x;
double y;
cin >> x >> y;
points_.emplace_back(x, y);
}
ConvexHullGraham ch(points_);
vector<pair<double, double>> ans = ch.GetConvexHull();
cout << ans.size() << '\n';
for (auto& it : ans) {
cout << fixed << setprecision(8) << it.first << " " << it.second << '\n';
}
return 0;
}