#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
std::pair<double, double> pivot;
void read_input(std::vector<std::pair<double, double> > &points, int &point_count) {
std::ifstream f("infasuratoare.in");
f >> point_count;
for (int i = 0; i < point_count; ++i) {
std::pair<double, double> p;
f >> p.first >> p.second;
points.push_back(p);
}
f.close();
}
double squared_distance(const std::pair<double, double> &p1, const std::pair<double, double> &p2) {
return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}
int orientation(const std::pair<double, double> &p1, const std::pair<double, double> &p2,
const std::pair<double, double> &p3) {
const double x = (p2.second - p1.second) * (p3.first - p1.first) - (p3.second - p1.second) * (p2.first - p1.first);
if (x == 0) return 0;
return (x > 0) ? 1 : -1; // 1=sens_trigonometric, -1=sens_orar
}
bool polar_angle_cmp(const std::pair<double, double> &a, const std::pair<double, double> &b) {
const int o = orientation(pivot, a, b);
if (o == 0) {
return squared_distance(pivot, a) < squared_distance(pivot, b);
}
return o == 1;
}
void grahams_scan(std::vector<std::pair<double, double> > &points, const int point_count) {
if (point_count < 3) {
return;
}
pivot = *std::ranges::min_element(
points, [](const std::pair<double, double> &a, const std::pair<double, double> &b) {
return (a.second < b.second) || (a.second == b.second && a.first < b.first);
});
std::ranges::sort(points, polar_angle_cmp);
std::vector<std::pair<double, double> > hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
for (int i = 2; i < point_count; ++i) {
while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) != 1) {
hull.pop_back();
}
hull.push_back(points[i]);
}
std::ofstream g("infasuratoare.out");
g << hull.size() << "\n";
for (const auto &[x, y]: hull) {
g << x << " " << y << "\n";
}
g.close();
}
int main() {
std::vector<std::pair<double, double> > points;
int point_count;
read_input(points, point_count);
grahams_scan(points, point_count);
return 0;
}