Cod sursa(job #698191)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 29 februarie 2012 12:51:53
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#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,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]-c)*(xm-l)<(x[i]-l)*(ym-c))++i;
while((ym-c)*(x[j]-l)<(xm-l)*(y[j]-c))--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);
}
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;
}
 double sqr( double z)
{
return z*z;
}
/*void elimina_pct()
{ int i,m,j;
   double max,z;
i=2; m=2;
while(i<=n)
    {
    max=sqrt(sqr(x[i]-l)+sqr(y[i]-c));
    j=i; x[m]=x[i]; y[m]=y[i];
    while(((y[j]-c)*(x[i]-l))==((x[j]-l)*(y[i]-c))&&i<=n)
        {
        z=sqrt(sqr(x[i]-l)+sqr(y[i]-c));
        if(z>=max){ x[m]=x[i]; y[m]=y[i]; max=z;}
        ++i;
        }
    ++m;
    }
n=m-1;
} */
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>1)--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;
}