// https://infoarena.ro/problema/infasuratoare
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdlib>
using namespace std;
#define MAX_SIZE 120001 // numarul maxim de puncte + 1
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 de comparare pentru qsort
int Compare(const void* a, const void* b) { // sortam punctele de la stanga la dreapta, de jos in sus
Point_t* pointA = (Point_t*)a;
Point_t* pointB = (Point_t*)b;
if (pointA->x < pointB->x) return -1;
if (pointA->x > pointB->x) return 1;
if (pointA->y < pointB->y) return -1;
if (pointA->y > pointB->y) return 1;
return 0;
}
// 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(MAX_SIZE); // punctele de intrare
for (int i = 0; i < N; i++) {
fin >> points[i].x >> points[i].y;
}
sort(points.begin(), points.begin() + N); // sortam punctele conform operatorului < definit
// Construirea infasuratoarei
vector<Point_t> hull; // stiva pentru a construi infasuratoarea
for (int i = 0; i < N; i++) {
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
}
// Afisam rezultatul
fout << hull.size() << "\n"; // afisam numarul de puncte din infasuratoare
for (int i = 0; i < hull.size(); i++) {
fout << hull[i].x << " " << hull[i].y << "\n"; // afisam coordonatele punctelor din infasuratoare
}
fin.close();
fout.close();
return 0;
}