Pagini recente » Cod sursa (job #2703942) | Cod sursa (job #1599625) | Cod sursa (job #1103990) | Cod sursa (job #19350) | Cod sursa (job #698661)
Cod sursa(job #698661)
#include <cstdio>
#include <cmath>
#define inf 1999999999
#define nmax 120005
using namespace std;
double x[nmax],y[nmax],l,c;
int n,k,st[nmax],ind;
void read()
{ int i;
double z;
freopen("infasuratoare.in","r",stdin); scanf("%d\n",&n);
l=inf; c=inf; ind=0;
for(i=1;i<=n;++i)
{
scanf("%lf %lf\n",&x[i],&y[i]);
if(x[i]<l){ l=x[i]; c=y[i]; ind=i; }
else if(x[i]==l&&y[i]<c){ c=y[i]; ind=i; }
}
z=x[1]; x[1]=x[ind]; x[ind]=z;
z=y[1]; y[1]=y[ind]; y[ind]=z;
fclose(stdin);
}
void qsort(int st,int dr)
{ int i,j;
double z,xm,ym;
i=st; j=dr;
xm=x[(st+dr)/2]; ym=y[(st+dr)/2];
do
{
// tg[i] < tg[mij]
while((y[i]-y[1])*(xm-x[1])<(x[i]-x[1])*(ym-y[1]))++i;
while((ym-y[1])*(x[j]-x[1])<(xm-x[1])*(y[j]-y[1]))--j;
if(i<=j)
{
z=x[i]; x[i]=x[j]; x[j]=z;
z=y[i]; y[i]=y[j]; y[j]=z;
++i; --j;
}
}
while(i<=j);
if(i<dr)qsort(i,dr);
if(st<j)qsort(st,j);
}
double sqr( double z)
{
return z*z;
}
void elimina_pct()
{ int i,m,j;
double max,z;
i=2; m=2;
do
{
max=sqrt(sqr(x[i]-x[1])+sqr(y[i]-y[1]));
j=i; x[m]=x[i]; y[m]=y[i];
while(((y[i]-y[1])*(x[j]-x[1]))==((x[i]-x[1])*(y[j]-y[1]))&&i<=n)
{
z=sqrt(sqr(x[i]-x[1])+sqr(y[i]-y[1]));
if(z>=max){ x[m]=x[i]; y[m]=y[i]; max=z;}
++i;
}
++m;
}
while(i<=n);
n=m-1;
}
int intoarce_dr(int c,int b,int a)
{ double z,q;
z=(x[b]-x[a])*(y[c]-y[a]);
q=(x[c]-x[a])*(y[b]-y[a]);
if(z<q)return 1;
else return 0;
}
void solve()
{ int i;
k=2; st[1]=1; st[2]=2;
for(i=3;i<=n;++i)
{
while(intoarce_dr(i,st[k],st[k-1])&&k>2)--k;
st[++k]=i;
}
}
void write()
{ int i;
freopen("infasuratoare.out","w",stdout); printf("%d\n",k);
for(i=1;i<=k;++i)printf("%lf %lf\n",x[st[i]],y[st[i]]);
fclose(stdout);
}
int main()
{
read();
qsort(2,n);
elimina_pct();
solve();
write();
return 0;
}