#include <bits/stdc++.h>
#include <type_traits>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including
using namespace std;
/*using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
typedef long long int ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpi> vvpi;
typedef vector<vpl> vvpl;
typedef set<int> si;
typedef multiset<int> msi;
typedef set<ll> sl;
typedef multiset<ll> msl;
#define clrcin cin.ignore(numeric_limits<streamsize>::max(),'\n');
#define GOGOGO ios::sync_with_stdio(false); cin.tie(nullptr);
#define BYEBYE return 0;
#define all(cn) (cn).begin(), (cn).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define repk(i, k, n) for(int i = k; i < n; ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define popcnt __builtin_popcount
#define gcd std::__detail::__gcd
#define lcm std::__detail::__lcm
const int INFI = 1e9 + 5;
const ll INFL = 4e18 + 5;
template<class T> void aread(T* arr, int ___n)
{
rep(i, ___n)
{
cin >> arr[i];
}
}
/************************************************* BEGIN GEOMETRY TEMPLATE *************************************************/
/************************************************* BEGIN GEOMETRY TEMPLATE *************************************************/
/************************************************* BEGIN GEOMETRY TEMPLATE *************************************************/
// helpful: https://cp-algorithms.com/geometry/basic-geometry.html#toc-tgt-7
/*
Helpful Notes:
vector can be represented with pt.
** dot product **
0. dot(a, b) = a.x * b.x + a.y * b.y
1. a*b = b*a
2. (crd*a)*b = crd*(a*b)
3. (a+b)*c = a*c + b*c
4. norm(v) = v*v
5. abs(v) = sqrt(norm(v)) // length of the vector
** cross product **
0. cross(a, b) = a.x * b.y - a.y * b.x
1. cross(a, b) = -cross(b, a)
2. cross(a, b) == 0 <=> a & b are collinear
3.
*/
typedef long double ld;
#define EPS ((ld)1e-9)
template<class crd> ll sgn(const crd& x) {
return x > ((crd)EPS) ? 1 : x < ((crd)-EPS) ? -1 : 0;
}
template<class crd> struct pt
{
crd x; crd y;
pt& operator=(const pt& other)
{
x=other.x; y=other.y;
return *this;
}
pt& operator+=(const pt& other)
{
x+=other.x; y+=other.y;
return *this;
}
pt& operator-=(const pt& other)
{
x-=other.x; y-=other.y;
return *this;
}
pt& operator*=(const crd& t)
{
x*=t; y*=t;
return *this;
}
pt& operator/=(const crd& t)
{
assert(t!=0);
x/=t; y/=t;
return *this;
}
pt operator+(const pt& other) const
{
return pt<crd>(*this) += other;
}
pt operator-(const pt& other) const
{
return pt<crd>(*this) -= other;
}
pt operator*(const crd& t) const
{
return pt<crd>(*this) *= t;
}
pt operator/(const crd& t) const
{
return pt<crd>(*this) /= t;
}
operator pt<ld>() const
{
pt<ld> newpt;
newpt.x = this->x; newpt.y = this->y;
return newpt;
}
};
template<class crd> pt<crd> operator*(const crd& t, const pt<crd>& pt)
{
return pt * t;
}
template<class crd> crd dot(const pt<crd>& l, const pt<crd>& r) // dot(l, r) = dot(r, l)
{
return l.x * r.x + l.y * r.y;
}
template<class crd> crd norm(const pt<crd>& a)
{
return dot(a, a);
}
template<class crd> ld abs(const pt<crd>& a)
{
return sqrtl(norm(a));
}
template<class crd> crd cross(const pt<crd>& l, const pt<crd>& r) // cross(l, r) = -cross(r, l)
{
return l.x * r.y - l.y * r.x;
}
template<class crd> bool upper(const pt<crd>& a) {
return ((a.y > 0) || (!a.y && a.x > 0));
}
template<class crd> bool operator<(const pt<crd> &a, const pt<crd> &b) {
if(upper(a) != upper(b)) return upper(a);
return cross(a, b) > 0;
}
bool operator<(const pt<ld> &a, const pt<ld> &b) {
return atan2(a.y, a.x) < atan2(b.y, b.x) - EPS;
}
/*
@ brief: find intersection of two lines (or their continuation)
NOTE: will crash due to division by 0 if lines are collinear
*/
pt<ld> intersection(const pt<ld>& a1, const pt<ld>& a2, const pt<ld>& b1, const pt<ld>& b2)
{
return a1 + ((a2 - a1) * cross(b1 - a1, b2 - b1) / cross(a2 - a1, b2 - b1));
}
template<class crd> bool intersection1d(crd l1, crd r1, crd l2, crd r2)
{
// note to self: this takes cases of the right and left points of the segment being flipped
if (l1 > r1)
{
r1 += l1;
l1 = r1 - l1;
r1 -= l1;
}
if (l2 > r2)
{
r2 += l2;
l2 = r2 - l2;
r2 -= l2;
}
return max(l1, l2) <= min(r1, r2) + ((crd)EPS);
}
/*
@ brief: whether or not two given line segments (a1-a2, b1-b2) intersect
*/
template<class crd> bool segseg(const pt<crd>& a1, const pt<crd>& a2, const pt<crd>& b1, const pt<crd>& b2) {
return intersection1d(a1.y, a2.y, b1.y, b2.y) && intersection1d(a1.x, a2.x, b1.x, b2.x) &&
sgn(cross(a1 - b1, b2 - b1)) * sgn(cross(a2 - b1, b2 - b1)) <= 0 &&
sgn(cross(b1 - a1, a2 - a1)) * sgn(cross(b2 - a1, a2 - a1)) <= 0;
}
/*
@ brief: area of polygon, points ordered by edge order
*/
template<class crd> ld polyarea(const vector<pt<crd>>& points)
{
int sz = points.size();
ld res = 0;
for(int i = 0; i < sz; ++i)
{
res += (ld)cross(points[i], points[(i==sz-1)?0:i+1]);
}
return abs(res / 2.0);
}
/*
@ brief: evaluate y value for a given x on a line
*/
ld evaluate_line(const pt<ld>& a, const pt<ld>& b, ld x)
{
if(abs(a.x - b.x) < EPS)
{
return a.y;
}
return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}
template<class crd> bool cw(const pt<crd>& o, const pt<crd>& a, const pt<crd>& b)
{
return cross(b-o, a-o) > 0;
}
template<class crd> bool ccw(const pt<crd>& o, const pt<crd>& a, const pt<crd>& b)
{
return cross(b-o, a-o) < 0;
}
template<class crd> void get_hull_side(const vector<pt<crd>>& gpts, vector<pt<crd>>& hull_side, bool side) // side=true => uppper, otherwise lower
{
if(gpts.size() <= 1)
{
return;
}
hull_side.push_back(gpts[0]);
int sz = gpts.size();
for(int i = 1; i < sz; ++i)
{
if(i == sz - 1 || ((side && cw(gpts[0], gpts[i], gpts[sz-1])) || (!side && ccw(gpts[0], gpts[i], gpts[sz-1]))))
{
while((int)hull_side.size() >= 2 && ((side && !cw(hull_side[(int)hull_side.size()-2], hull_side[(int)hull_side.size()-1], gpts[i])) ||
(!side && !ccw(hull_side[(int)hull_side.size()-2], hull_side[(int)hull_side.size()-1], gpts[i]))))
{
hull_side.pop_back();
}
hull_side.push_back(gpts[i]);
}
}
}
/*
@ brief: get convex hull of points, output sorted by trigonometric order
*/
template<class crd> vector<pt<crd>> convex_hull(vector<pt<crd>> pts) // replace to reference if you need the sorted order later
{
if(pts.size() <= 1)
{
return vector<pt<crd>>();
}
vector<pt<crd>> hull;
vector<pt<crd>> upper;
vector<pt<crd>> lower;
sort(all(pts), [](const pt<crd>& a, const pt<crd>& b){return a.x < (b.x - ((crd)EPS)) || ((a.x - b.x) < ((crd)EPS) && a.y < (b.y - ((crd)EPS)));}); // sorting for graham's scan
get_hull_side(pts, upper, true);
get_hull_side(pts, lower, false);
int usz = upper.size();
int lsz = lower.size();
//cout << upper.size() << endl;
for(int i = usz - 1; i >= 0; --i)
{
hull.pb(upper[i]);
}
for(int i = 1; i < lsz - 1; ++i)
{
hull.pb(lower[i]);
}
return hull;
}
int main()
{
freopen("winding.in", "r", stdin);
freopen("winding.out", "w", stdout);
cout << fixed << setprecision(6);
int n; cin >> n;
vector<pt<ld>> in(n);
rep(i, n)
{
cin >> in[i].x >> in[i].y;
}
vector<pt<ld>> ch = convex_hull(in);
cout << ch.size() << endl;
for(auto e : ch)
{
cout << e.x << " " << e.y << endl;
}
return 0;
}