Pagini recente » Cod sursa (job #2383006) | Cod sursa (job #968550) | Cod sursa (job #1669676) | Cod sursa (job #1835756) | Cod sursa (job #1529467)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct punct
{
double x,y;
}v[120001];
int stiva_down[120001],f[120001],stiva_up[120001];
int angle_down(int a,int o,int b)
{
if(v[o].y<v[a].y || v[o].y<v[b].y)
return 1;
return 0;
}
int angle_up(int a,int o,int b)
{
if(v[o].y>v[a].y || v[o].y>v[b].y)
return 1;
return 0;
}
void quicksort(int p,int u)
{
int j,i;
double pivot,aux;
if(p<u)
{
pivot=v[(p+u)/2].x;
i=p;
j=u;
while(i<=j)
{
while(v[i].x<pivot && i<u)
i++;
while(v[j].x>pivot && j>p)
j--;
if(i<=j){
aux=v[i].x;
v[i].x=v[j].x;
v[j].x=aux;
if((v[i].y>v[j].y && v[j].x==v[i].x) || v[j].x>v[i].x)
{
aux=v[i].y;
v[i].y=v[j].y;
v[j].y=aux;
}
i++;
j--;
}
}
if(p<j)
quicksort(p,j);
if(i<u)
quicksort(i,u);
}
}
int main()
{
int n,i,d,u;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
quicksort(1,n);
stiva_down[1]=1;
d=1;
for(i=2; i<=n; i++)
{
while(d>1 && !angle_down(stiva_down[d-1],stiva_down[d],i))
d--;
stiva_down[++d]=i;
}
stiva_up[1]=1;
u=1;
for(i=2; i<=n; i++)
{
while(u>1 && !angle_up(stiva_up[u-1],stiva_up[u],i))
u--;
stiva_up[++u]=i;
}
printf("%d\n",u+d-2);
for(i=1; i<=d; i++)
printf("%.6lf %.6lf\n",v[stiva_down[i]].x,v[stiva_down[i]].y);
for(i=u-1; i>1; i--)
printf("%.6lf %.6lf\n",v[stiva_up[i]].x,v[stiva_up[i]].y);
return 0;
}