//algoritmi sunt implementati bazandu-ma pe pseudocodul de aici http://gta.math.unibuc.ro/stup/geom_comp.pdf
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <deque>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
#define foreach(i,n) for(int i = 0; i < n ; i++)
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const long double epsilon = 10e-15;
//algoritmul lent infasuratoare convexa O(n^4)c
struct Point
{
long double x,y,pa,pd;
Point(){x = 0; y = 0; pa= 0; pd = 0;}
Point(long double xx,long double yy){ x = xx; y = yy; pa= 0 ; pd= 0 ;}
friend istream& operator >>( istream& i , Point& p );
friend ostream& operator <<( ostream& o, Point&p );
friend ostream& operator<<( ostream&o, const Point& p );
bool operator != ( const Point& B );
bool operator != ( const Point& B )const;
bool operator ==( const Point&B )const;
Point operator /=( long double divide );
Point operator +=( const Point& );
long double distanceFrom( const Point &B );
long double distanceFrom( const Point &B )const;
bool isRight( const Point &A, const Point& B )const;
bool isLeft( const Point &A, const Point& B )const;
bool isOn( const Point &A, const Point& B )const;
long double polarAngle( const Point& p0 );
long double polarDistance( const Point& p0 );
bool orientation( Point p0,Point p1, Point p2);
};
bool orientation( Point p0,Point p1, Point p2)
{
Point p1prim,p2prim;
p1prim.x = p1.x - p0.x;
p1prim.y = p1.y - p0.y;
p2prim.x = p2.x - p0.x;
p2prim.y = p2.y - p0.y;
return (p1prim.x * p2prim.y - p2prim.x * p1prim.y > 0);
}
long double Point::polarAngle(const Point& p0)
{
return atan2((long double)(y-p0.y),(long double)(x-p0.x));
}
long double Point::polarDistance(const Point& p0)
{
return sqrt( ( x-p0.x )*( x - p0.x ) + ( y - p0.y )*( y - p0.y ) );
}
long double determinant(const Point&P, const Point& Q, const Point&R)
{
return ( Q.x * R.y + P.x * Q.y + R.x * P.y - Q.x * P.y - R.x * Q.y - P.x * R.y);
}
bool Point::isRight(const Point &A, const Point& B)const
{
return ( determinant(A, B, *this)<0);
}
bool Point::isOn(const Point &A, const Point& B)const
{
return ( determinant(A, B, *this) == 0);
}
bool Point::isLeft(const Point &A, const Point& B)const
{
return (determinant(A, B, *this) > 0);
}
Point Point::operator +=(const Point& B)
{
x += B.x;
y += B.y;
return *this;
}
Point Point::operator /=(long double divide)
{
x /= divide;
y /= divide;
return *this;
}
bool Point::operator !=(const Point& B)
{
if (x == B.x && y == B.y)
return false;
return true;
}
bool Point::operator ==(const Point&B)const
{
if( x == B.x && y == B.y)
return true;
return false;
}
bool Point::operator !=(const Point& B)const
{
if (x == B.x && y == B.y)
return false;
return true;
}
istream& operator>>(istream& i , Point& p)
{
i >> p.x >> p.y;
return i;
}
ostream& operator<<(ostream& o , Point&p)
{
o<< fixed << setprecision(2) << p.x<< " "<< fixed << setprecision(2) <<p.y;
return o;
}
ostream& operator<<(ostream&o,const Point& p)
{
o<<fixed<<setprecision(6)<<p.x<<" "<<fixed<<setprecision(6)<<p.y<<'\n';
return o;
}
Point gCenter(const vector<Point>& M)
{
Point p;
for(const auto& point:M)
p += point;
p /=M.size();
return p;
}
long double area( const Point& A, const Point& B, const Point& C)
{
return abs((1.0/2.0)*( A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.x * C.y - A.y * B.x));
}
long double Point::distanceFrom(const Point& B)
{
return abs( sqrt( (B.x - x ) * ( B.x - x) + (B.y - y) * (B.y - y) ));
}
long double Point::distanceFrom(const Point& B)const
{
return abs(sqrt( (B.x - x ) * ( B.x - x ) + ( B.y - y) * ( B.y - y) ));
}
bool PinsideOrEdges(const Point& p, const Point& A, const Point& B, const Point& C)
{
bool value = false;
if ( abs((area(A,B,C)- (area(p,A,B)+area(p,A,C)+area(p,B,C)) )) <epsilon)
value = true;
if ( abs( A.distanceFrom(B) - (A.distanceFrom(p) + p.distanceFrom(B) ) ) <epsilon && p!=A && p!= B)
value = true;
if ( abs(A.distanceFrom(C) - (A.distanceFrom(p) + p.distanceFrom(C) ) ) <epsilon && p!=A && p!= C)
value = true;
if ( abs(B.distanceFrom(C) - (B.distanceFrom(p) + p.distanceFrom(C) ) ) <epsilon && p!=B && p!= C)
value = true;
return value;
}
void Grahams_Scan_Convex_Hull(vector<Point>&P)
//O(nlogn) here is a good example+pseudocod https://www.youtube.com/watch?v=QYrpHE8iDGg
//also we can test here https://www.mathsisfun.com/data/cartesian-coordinates-interactive.html
{
//sortam punctele
Point p0(1000000000,1000000000);
stack<Point> s;
for( auto &p:P)
if(p.y<p0.y)
p0 = p;
else
if(p.y == p0.y)
if( p.x < p0.x)
p0 = p;
for(auto p = P.begin();p!=P.end(); p++)
{
p->pa = p->polarAngle(p0);
p->pd = p->polarDistance(p0);
}
sort(P.begin(),P.end(),[=](Point a,Point b)->bool{ return orientation(p0,a,b);});
for(auto it = P.begin() ; it!=P.end() ; it++)
if( it+1 !=P.end() && abs( abs(it->pa)-abs( (it+1)->pa))<= epsilon)
if(it->pd>(it+1)->pd)
P.erase(it+1);
else
P.erase(it);
auto it = P.begin();
s.push(*it);
s.push(*(it+1));
s.push(*(it+2));
Point p1,p2,pi;
for(auto p = it+3; p!=P.end() ; p++)
{
pi = *p;
p2 = s.top();
s.pop();
p1 = s.top();
s.push(p2);
while( pi.isRight(p1,p2) || pi.isOn(p1,p2))
{
s.pop();
p2 = p1;
s.pop();
p1 = s.top();
s.push(p2);
}
s.push(pi);
}
deque<Point> dP;
while(!s.empty())
{
dP.push_front(s.top());
s.pop();
}
out<<dP.size()<<'\n';
for(const auto& it:dP)
out<<it;
}
int main()
{
int n;
in>>n;
Point p;
vector<Point> P;
foreach(i,n)
{
in>>p;
P.push_back(p);
}
Grahams_Scan_Convex_Hull(P);
return 0;
}