//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 <list>
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;
const int MAX_VALUE_X = 1000000000;
const int MAX_VALUE_Y = 1000000000;
const int Min_VALUE_X = -1000000000;
const int Min_VALUE_Y = -1000000000;
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& );
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)
{
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);//p1 in dreapta lu p2
}
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;
Point p(x,y);
return p;
}
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 list<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 list<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,list<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));
}
}
list< Point > firstSlowAlg(const vector<Point>& P)//O(n^4)
{
list< Point > Hull;
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)
Hull.push_back(p);
}
Point gCen = gCenter(Hull);
Hull.sort([=](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 ) ; });
return Hull;
}
list <Point>secondSlowAlg(const vector<Point>&P)//O(n^3)
{
vector<pair<Point,Point>>E;
list<Point> Hull;
solvesecondSlowAlg(P,E,true);
solvesecondSlowAlg(P,E,false);
add(E,Hull);
Point gCen = gCenter(Hull);
Hull.sort([=](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); });
return Hull;
}
list<Point> 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;
p0.x = p0.MAX_VALUE_X;
p0.y = p0.MAX_VALUE_Y;
vector<Point>::iterator ite;
stack<Point> s;
for( auto p= P.begin() ; p!=P.end() ; p++)
if(p->y<p0.y)
p0 = *p,ite = p;
else
if(p->y == p0.y)
if( p->x < p0.x)
p0 = *p,ite = p;
swap(*ite,*P.begin());
for(auto p = P.begin()+1;p!=P.end(); p++)
{
p->pa = p->polarAngle(p0);
p->pd = p->polarDistance(p0);
}
sort(P.begin()+1,P.end(),[=](Point a,Point b)->bool{
if (a.pa<b.pa)
return true;
else
{
if (abs( abs(a.pa)-abs(b.pa))<= epsilon)
{
return (a.pd < b.pd);
}
return false;
}
});
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);
}
list <Point > Hull;
while(!s.empty())
{
Hull.push_front(s.top());
s.pop();
}
return Hull;
}
list<Point > Jarvis_March( vector<Point>& P)//O(nh)
{
Point p0;
p0.x = p0.MAX_VALUE_X;
p0.y = p0.MAX_VALUE_Y;
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;
list< Point > Hull;
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);
}
for(const auto &p :L)
Hull.push_back(p);
return Hull;
}
std ::list< Point > Grahams_Scan_Convex_Hull_orientationTest( 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;
p0.x = p0.MAX_VALUE_X;
p0.y = p0.MAX_VALUE_Y;
stack<Point> s;
vector< Point>::iterator ite;
for( auto p = P.begin(); p != P.end() ; p++)
if(p->y<p0.y)
p0 = *p,
ite = p;
else
if(p->y == p0.y)
if( p->x < p0.x)
p0 = *p,
ite = p;
swap(*ite,*P.begin());
sort(P.begin()+1,P.end(),[=](Point a,Point b)->bool{ return orientation(p0,a,b);});
auto it = P.begin()+1;
s.push(p0);
s.push(*it);
s.push(*(it+1));
Point p1,p2,pi;
for(auto p = it+2; p!=P.end() ; p++)
{
pi = *p;
p2 = s.top();
s.pop();
p1 = s.top();
s.push(p2);
while( !orientation(p1,p2,pi))
{
s.pop();
p2 = p1;
s.pop();
p1 = s.top();
s.push(p2);
}
s.push(pi);
}
list< Point > hull;
while(!s.empty())
{
hull.push_front(s.top());
s.pop();
}
return hull;
}
int main()
{
int n;
in>>n;
Point p;
vector<Point> P;
list< Point > ConvexHull;
foreach(i,n)
{
in>>p;
P.push_back(p);
}
int op=4;
//cout<<"1-FirstSlowAlg\n2-SecondSlwAlg\n3 cu unghi polar 5 cu orientare-Grahams Scan\n4-Jarvis'March\n";
//cin>>op;
switch(op)
{
case 1: ConvexHull = firstSlowAlg(P); break;
case 2: ConvexHull = secondSlowAlg(P); break;
case 3: ConvexHull = Grahams_Scan_Convex_Hull(P); break;
case 4: ConvexHull = Jarvis_March(P); break;
case 5: ConvexHull = Grahams_Scan_Convex_Hull_orientationTest(P); break;
}
out << ConvexHull.size()<<'\n';
for(const auto& p:ConvexHull)
out << p;
return 0;
}