#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define pi 3.14159265
typedef struct
{
double x,y;
}Punct;
Punct start;
typedef struct
{
double x,y;
}Vector;
struct Node
{
Punct *p;
struct Node *ant;
};
typedef struct
{
int size;
struct Node *head;
}Stack;
Stack *createStack()
{
Stack *s=malloc(sizeof(Stack));
s->size=0;
s->head=NULL;
return s;
}
void pushStack(Stack *s,Punct *p)
{
struct Node *n=malloc(sizeof(struct Node));
n->p=p;
n->ant=s->head;
s->head=n;
s->size++;
}
void popStack(Stack *s)
{
if(s->head!=NULL)
{
struct Node *aux=s->head;
s->head=s->head->ant;
free(aux);
s->size--;
}
}
void deleteStack(Stack *s)
{
while(s->head!=NULL)
popStack(s);
free(s);
}
void reverseStack(Stack **s)
{
Stack *aux=*s;
*s=createStack();
while(aux->head!=NULL)
{
pushStack(*s,aux->head->p);
popStack(aux);
}
free(aux);
}
void printStack(Stack *s,FILE *out)
{
struct Node *n=s->head;
while(n)
{
fprintf(out,"%lf %lf\n",n->p->x,n->p->y);
n=n->ant;
}
}
int isSmaller(Punct *a,Punct *b)
{
if(a->y > b->y)
return 0;
if((a->y < b->y) || (a->x < b->x))
return 1;
return 0;
}
Vector createVector(Punct *a,Punct *b)
{
Vector v;
v.x=b->x - a->x;
v.y=b->y - a->y;
return v;
}
double magnitude(Vector v)
{
return sqrt(v.x*v.x + v.y*v.y);
}
double dotProd(Vector a,Vector b)
{
return a.x*b.x + a.y*b.y;
}
double cosVector(Vector a,Vector b)
{
return dotProd(a,b)/(magnitude(a)*magnitude(b));
}
int compar(const void *a,const void *b)
{
Punct *punct_a=(Punct *)a;
Punct *punct_b=(Punct *)b;
if(punct_a->x==start.x && punct_a->y==start.y)
return -1;
if(punct_b->x==start.x && punct_b->y==start.y)
return 1;
Vector va=createVector(&start,punct_a);
Vector vb=createVector(&start,punct_b);
Vector i= {1,0};
double cos_va=cosVector(va,i);
double cos_vb=cosVector(vb,i);
if(cos_va>cos_vb)
return -1;
if(cos_va<cos_vb)
return 1;
return 0;
}
Vector getLeftDirection(Vector v)
{
int sign= v.y>=0?1:-1;
Vector i= {1,0};
double radial_angle=sign*acos(cosVector(v,i));
double leftDirection_angle=pi/2+radial_angle;
Vector leftDirection= {cos(leftDirection_angle),sin(leftDirection_angle)};
return leftDirection;
}
int leftTurn(Vector v0,Vector v1)
{
Vector n=getLeftDirection(v0);
return dotProd(n,v1)>0;
}
void infasuratoare(Punct *p,int n,FILE *out)
{
Vector anterior,curent;
Stack *s=createStack();
qsort(p,n,sizeof(Punct),compar);
anterior=createVector(p,p+1);
pushStack(s,p);
pushStack(s,p+1);
for(int i=2;i<n;i++)
{
curent=createVector(s->head->p,p+i);
while(!leftTurn(anterior,curent))
{
popStack(s);
curent=createVector(s->head->p,p+i);
anterior=createVector(s->head->ant->p,s->head->p);
}
pushStack(s,p+i);
anterior=curent;
}
fprintf(out,"%d\n",s->size);
reverseStack(&s);
printStack(s,out);
deleteStack(s);
}
int main()
{
int n;
Punct p[120000];
FILE *in=fopen("infasuratoare.in","r"),*out=fopen("infasuratoare.out","w");
fscanf(in,"%d",&n);
fscanf(in,"%lf %lf",&(p[0].x),&(p[0].y));
start=p[0];
for(int i=1;i<n;i++)
{
fscanf(in,"%lf %lf",&(p[i].x),&(p[i].y));
if(isSmaller(p+i,&start))
start=p[i];
}
infasuratoare(p,n,out);
fclose(in);
fclose(out);
return 0;
}