Cod sursa(job #696519)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 28 februarie 2012 18:50:34
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#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,mij;
  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;
}
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;
    ++k; st[k]=i;
    }
}
void write()
{ int i;
freopen("infasuratoare.out","w",stdout); printf("%d\n",k);
for(i=2;i<=k;++i)printf("%.6lf %.6lf\n",x[st[i]],y[st[i]]);
printf("%.6lf %.6lf\n",x[1],y[1]);
fclose(stdout);
}
int main()
{
read();
qsort(2,n);
solve();
write();
return 0;
}