NOIC CH nlog.cpp

//Código por Pedro Bignotto Racchetti
//O(nlogn)

#include<bits/stdc++.h>
using namespace std;


struct Pt {
	int x, y;
	Pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
	Pt operator+(const Pt& o) { return Pt(x+o.x, y+o.y); } // soma de vetores
	Pt operator-(const Pt& o) { return Pt(x-o.x, y-o.y); } // subtração de vetores
	bool operator < (Pt o) const{ // ordena pelas abscissas e depois pelas ordenadas
        if(x == o.x) return y < o.y;
        return x < o.x;
    }
	void operator+=(const Pt& o) { x += o.x, y += o.y; } // somar vetores com o operador +=
	void operator-=(const Pt& o) { x -= o.x, y -= o.y; } // subtrair vetores com o operador -=
	long long dot(const Pt& o) { return 1ll*x*o.x + 1ll*y*o.y; } // dot - produto escalar
	long long cross(const Pt& o) { return 1ll*x*o.y - 1ll*y*o.x; } // cross - produto vetorial
};

Pt pts[112345];
int marc[112345];
int n;
vector<Pt> conv, upper, lower;
void makeconv(){
	long long it1 = 0, it2 = 0;
	for(int i = 0; i < n; i++){
		if(marc[i]) continue;
		while(it1 >= 2 && (pts[i] - upper[it1 - 2]).cross(upper[it1 - 1] - upper[it1 -2]) < 0){
			upper.pop_back();
			it1--;
		}
		upper.push_back(pts[i]);
		it1++;
		while(it2 >= 2 && (pts[i] - lower[it2 - 2]).cross(lower[it2 - 1] - lower[it2 -2]) > 0){
			lower.pop_back();
			it2--;
		}
		lower.push_back(pts[i]);
		it2++;
	}
	for(int i = 0; i < it1 - 1; i++)	conv.push_back(upper[i]);
	for(int i = it2 - 1; i > 0; i--)	conv.push_back(lower[i]);
}



int main(){
	scanf("%d", &n);
	
	
	for(int i = 0; i < n; i++){
		scanf("%lld %lld", &pts[i].x, &pts[i].y);

	}
	sort(pts, pts + n);
	makeconv();
	printf("%lu\n", conv.size());
	for(int i = 0; i < conv.size(); i++ ){
		printf("%lld %lld\n", conv[i].x, conv[i].y);
	}
	scanf("%d", &n);
	



}