Cod sursa(job #779069)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
#define x first
#define y second
typedef pair<double,double> Pair;
const int Nmax = 120011 ;
int N,Size;
Pair A[Nmax];
int St[Nmax],Rez[Nmax];
int Ecu ( Pair A , Pair B , Pair P )
{
double a = A.y - B.y ;
double b = B.x - A.x ;
double c = - A.y * B.x + B.y * A.x ;
if ( a*P.x + b*P.y + c > 0 ) return 1;
if ( a*P.x + b*P.y + c < 0 ) return -1;
return 0;
}
#define EPS 1e-12
inline int cmp(double a, double b)
{
if (a + EPS < b) return -1;
if (b + EPS < a) return +1;
return 0;
}
#undef EPS
int cmp_Pair(const Pair &a, const Pair& b)
{
int r = cmp(a.x, b.x);
if (r != 0) return r == -1;
return cmp(a.y, b.y) == -1;
}
void Andrew()
{
sort(A+1,A+N+1,cmp_Pair);
St[++Size] = 1;
for (int i=2;i<N;++i)
if ( Ecu ( A[N] , A[1] , A[i] ) < 0 )
{
St[++Size] = i;
if ( Size > 2 )
while ( Size > 2 )
{
if ( Ecu ( A[St[Size-2]] , A[St[Size]] , A[St[Size-1]] ) <= 0 )
St[Size-1]=St[Size],
--Size,
St[Size+1]=0;
else
break;
}
}
for (int i=1;i<=Size;++i)
Rez[++Rez[0]]=St[i],
St[i]=0;
Size=0;
St[++Size] = N;
for (int i=N-1;i>1;--i)
if ( Ecu ( A[1] , A[N] , A[i] ) < 0 )
{
St[++Size] = i;
if ( Size > 2 )
while ( Size > 2 )
{
if ( Ecu ( A[St[Size-2]] , A[St[Size]] , A[St[Size-1]] ) <= 0 )
St[Size-1]=St[Size],
--Size,
St[Size+1]=0;
else
break;
}
}
for (int i=1;i<=Size;++i)
Rez[++Rez[0]]=St[i],
St[i]=0;
}
ifstream F("infasuratoare.in");
ofstream G("infasuratoare.out");
int main()
{
F>>N;
for (int i=1;i<=N;++i)
F>>A[i].x>>A[i].y;
Andrew();
G<<Rez[0]<<'\n';
for (int i=Rez[0];i;--i)
G<<fixed<<setprecision(6)<<A[Rez[i]].x<<' '<<A[Rez[i]].y<<'\n';
}