Pagini recente » Cod sursa (job #1370385) | Cod sursa (job #521109) | Cod sursa (job #2743561) | Cod sursa (job #2402948) | Cod sursa (job #1529660)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct punct
{
double x,y;
}v[120001];
int stiva[120001],f[120001];
long double determinant(int A,int C,int B) {
return (long double)v[A].x * v[B].y
+ (long double)v[B].x * v[C].y
+ (long double)v[C].x * v[A].y
- (long double)v[C].x * v[B].y
- (long double)v[A].x * v[C].y
- (long double)v[B].x * v[A].y;
}
void quicksort(int p,int u)
{
int j,i;
long 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[1]=1;
u=1;
for(i=2; i<=n; i++)
{
while(u>1 && determinant(stiva[u-1],stiva[u],i)<=0.0)
u--;
stiva[++u]=i;
}
for(i=n-1; i>=1; i--)
{
while(u>1 && determinant(stiva[u-1],stiva[u],i)<=0.0)
u--;
stiva[++u]=i;
}
printf("%d\n",u-1);
for(i=u; i>1; i--)
printf("%.6lf %.6lf\n",v[stiva[i]].x,v[stiva[i]].y);
return 0;
}