//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>
#include <map>
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 = 0.00000000000000000001;
//algoritmul lent infasuratoare convexa O(n^4)
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&);
};
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;
}
bool isInside(const Point& edge,const vector<Point> &L)
{
bool is = false;
for(const auto& isin:L)
if (isin == edge)
is = true;
return is;
}
void add(const vector<pair<Point,Point>>&E,vector<Point> &L)
{
for(const auto& edges:E)
{
if(!isInside(edges.first,L))
L.push_back(edges.first);
if(!isInside(edges.second,L))
L.push_back(edges.second);
}
}
void solvesecondSlowAlg(const vector<Point>& P,vector<pair<Point,Point>>&E,bool rightOrientation)
{
bool valid;
for(const auto& p:P)
for(const auto& q:P)
if(p != q)
{
valid = true;
for(const auto& r:P)
if( r!=p && r!=q)
{
if(rightOrientation)
if (r.isRight(p,q))
valid = false;
if(!rightOrientation)
if (r.isLeft(p,q))
valid = false;
}
if(valid)
E.push_back(make_pair(p,q));
}
}
void firstSlowAlg(const vector<Point>& P)//O(n^4)
{
vector<Point> M;
bool valid;
for(const auto& p:P)
{
valid = true;
for(const auto& A:P)
for(const auto& B:P)
for(const auto& C:P)
if (A!=p && B!=p && C!=p && A!=B && A!=C && B!=C)
if (PinsideOrEdges(p,A,B,C))
valid = false;
if( valid == true)
M.push_back(p);
}
Point gCen = gCenter(M);
sort(M.begin(),M.end(),[=](const Point& A,const Point& B){return atan2(A.y-gCen.y,A.x-gCen.x)<atan2(B.y-gCen.y,B.x-gCen.x); });
out<<M.size()<<'\n';
for(const auto& P:M)
out<<P;
}
void secondSlowAlg(const vector<Point>&P)//O(n^3)
{
vector<pair<Point,Point>>E;
vector<Point>L;
solvesecondSlowAlg(P,E,true);
solvesecondSlowAlg(P,E,false);
add(E,L);
add(E,L);
Point gCen = gCenter(L);
sort(L.begin(),L.end(),[=](const Point& A,const Point& B)->bool{return atan2(A.y-gCen.y,A.x-gCen.x)<atan2(B.y-gCen.y,B.x-gCen.x); });
out<<L.size()<<'\n';
for(const auto& p:L)
out<<p;
}
bool anglemakesanonleftturn(Point a,Point b, Point c)
{
return (determinant(a,b,c)<=0);
}
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 dupa unghiul polar si distanta polara
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 (a.pa<b.pa);});
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;
}
void Jarvis_March( vector<Point>& P)
{
Point p0(1000000000,1000000000);
for( auto &p:P)
if(p.y<p0.y)
p0 = p;
else
if(p.y == p0.y)
if( p.x < p0.x)
p0 = p;
vector<Point> L;
vector<Point>::iterator it2,rp;
Point lp;
L.push_back(p0);
while(true)
{
lp = L.back();
rp = P.begin();
for(auto it = P.begin()+1; it!= P.end() ;it++)
if( it-> isRight(lp, *rp) || it -> isOn(lp, *rp) )
if (it->isRight(lp,*rp))
rp = it;
else
rp = (lp.distanceFrom(*rp)>lp.distanceFrom(*it))?rp:it;
if (*rp == p0)
break;
L.push_back(*rp);
P.erase(rp);
}
out<<L.size()<<'\n';
for(const auto &p :L)
out<<p;
}
int main()
{
int n;
in>>n;
Point p;
vector<Point> P;
foreach(i,n)
{
in>>p;
P.push_back(p);
}
int op=4;
//cout<<"1-FirstSlowAlg\n2-SecondSlwAlg\n3-Grahams Scan\n4-Jarvis'March\n";
//cin>>op;
switch(op)
{
case 1: firstSlowAlg(P); return 0;
case 2: secondSlowAlg(P); return 0;
case 3: Grahams_Scan_Convex_Hull(P); return 0;
case 4: Jarvis_March(P); return 0;
}
return 0;
}