// https://infoarena.ro/problema/infasuratoare
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
struct Point_t {
double x;
double y;
bool operator<(const Point_t& other) const { // operator de comparare pentru sortare: sortam punctele de la stanga la dreapta, de jos in sus
if (x != other.x) {
return x < other.x;
}
return y < other.y;
}
};
// Functie pentru a verifica daca doua puncte sunt egale
bool isEqual(const Point_t& a, const Point_t& b) {
return (a.x == b.x && a.y == b.y);
}
// Functia pentru calcularea produsului vectorial -> folosita pentru a verifica orientarea punctelor (unghi stanga sau dreapta)
// > 0 : c e la stanga lui a -> b
// = 0 : c e colinear cu a si b
// < 0 : c e la dreapta lui a -> b
double CrossProduct(const Point_t& a, const Point_t& b, const Point_t& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
// Functie care construieste infasuratoarea convexa a multimii de pncte date
vector<Point_t> ConvexHull(const vector<Point_t>& points) {
vector<Point_t> hull; // infasuratoarea
vector<Point_t> lower, upper; // jumatatile inferioara si superioara ale infasuratoarei
int n = points.size();
if (n < 3) return hull; // daca avem mai putin de 3 puncte, nu putem forma un poligon
for (int i = 0; i < n; i++) {
while (lower.size() >= 2 && CrossProduct(lower[lower.size() - 2], lower.back(), points[i]) <= 0) {
lower.pop_back(); // eliminam ultimul punct daca nu formeaza un unghi stang
}
lower.push_back(points[i]);
}
for (int i = n - 1; i >= 0; i--) {
while (upper.size() >= 2 && CrossProduct(upper[upper.size() - 2], upper.back(), points[i]) <= 0) {
upper.pop_back(); // eliminam ultimul punct daca nu formeaza un unghi stang
}
upper.push_back(points[i]);
}
// Eliminam ultimul punct din fiecare jumatate, deoarece ele sunt egale cu primul punct din cealalta jumatate
lower.pop_back();
upper.pop_back();
// Combinam cele doua jumatati pentru a forma infasuratoarea completa
hull = lower;
hull.insert(hull.end(), upper.begin(), upper.end());
return hull;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
fin >> N;
vector<Point_t> points(N); // punctele de intrare
for (int i = 0; i < N; i++) {
fin >> points[i].x >> points[i].y;
}
sort(points.begin(), points.end()); // sortam punctele conform operatorului < definit
points.erase(unique(points.begin(), points.end(), isEqual), points.end()); // eliminam punctele duplicate
vector<Point_t> hull = ConvexHull(points);
// Afisarea rezultatului
fout << hull.size() << endl;
fout << setprecision(6) << fixed;
for (int i = 0; i < (int)hull.size(); i++) {
fout << hull[i].x << " " << hull[i].y << endl;
}
fin.close();
fout.close();
return 0;
}