// https://infoarena.ro/problema/infasuratoare
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdlib>
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;
}
};
// 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);
}
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
// Construirea infasuratoarei
vector<Point_t> hull; // stiva pentru a construi infasuratoarea
for (int i = 0; i < N; i++) { // partea de sus
while (hull.size() >= 2) {
if (CrossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
hull.pop_back(); // eliminam ultimul punct daca orientarea nu este stanga
}
else {
break; // daca orientarea este stanga, iesim din bucla
}
}
hull.push_back(points[i]); // adaugam punctul curent in infasuratoare
}
int M = hull.size(); // numarul de puncte din partea de sus a infasuratoarei
for (int i = N - 2; i >= 0; i--) { // partea de jos
while (hull.size() > M) {
if (CrossProduct(hull[hull.size() - 2], hull.back(), points[i]) <= 0) {
hull.pop_back(); // eliminam ultimul punct daca orientarea nu este stanga
}
else {
break; // daca orientarea este stanga, iesim din bucla
}
}
hull.push_back(points[i]); // adaugam punctul curent in infasuratoare
}
//// Eliminam ultimul punct (pentru a evita duplicarea)
//if (hull.size() > 1) {
// hull.pop_back();
//}
// Afisam rezultatul
fout << hull.size() << "\n"; // afisam numarul de puncte din infasuratoare
for (int i = 1; i < hull.size(); i++) {
fout << hull[i].x << " " << hull[i].y << "\n"; // afisam coordonatele punctelor din infasuratoare
}
fin.close();
fout.close();
return 0;
}