Pagini recente » Cod sursa (job #3264701) | Cod sursa (job #400220) | Cod sursa (job #1406316) | Cod sursa (job #2231975) | Cod sursa (job #1529605)
#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];
double determinant(int A,int C,int B) {
return v[A].x * v[B].y
+ v[B].x * v[C].y
+ v[C].x * v[A].y
- v[C].x * v[B].y
- v[A].x * v[C].y
- v[B].x * v[A].y;
}
int unghi(int a,int o,int b)
{
if(determinant(a,o,b)<0)
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 && !unghi(stiva_down[d-1],stiva_down[d],i))
d--;
stiva_down[++d]=i;
}
stiva_up[1]=n;
u=1;
for(i=n-1; i>=1; i--)
{
while(u>1 && !unghi(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=2; i<u; i++)
printf("%.6lf %.6lf\n",v[stiva_up[i]].x,v[stiva_up[i]].y);
return 0;
}