// https://infoarena.ro/problema/infasuratoare
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
#define MAX_SIZE 120001 // numarul maxim de puncte + 1
struct Point_t {
double x;
double y;
};
Point_t points[MAX_SIZE]; // punctele de intrare
Point_t hull[MAX_SIZE]; // infasuratoarea convexa
// 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)
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;
for (int i = 0; i < N; i++) {
fin >> points[i].x >> points[i].y;
}
// Sortare puncte
qsort(points, N, sizeof(Point_t), Compare);
// Construirea infasuratoarei convexe
int hullSize = 0;
for (int i = 0; i < N; i++) {
while (hullSize >= 2 && CrossProduct(hull[hullSize - 2], hull[hullSize - 1], points[i]) <= 0) { // verificare orientare
hullSize--;
}
hull[hullSize++] = points[i];
}
for (int i = N - 2, t = hullSize + 1; i >= 0; i--) {
while (hullSize >= t && CrossProduct(hull[hullSize - 2], hull[hullSize - 1], points[i]) <= 0) { // verificare orientare
hullSize--;
}
hull[hullSize++] = points[i];
}
// Eliminarea ultimului punct adaugat, care este egal cu primul
hullSize--;
// Scrierea rezultatului
fout << hullSize << endl;
for (int i = 0; i < hullSize; i++) {
fout << hull[i].x << " " << hull[i].y << endl;
}
fin.close();
fout.close();
return 0;
}