Cod sursa(job #2389593)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 27 martie 2019 11:54:29
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include<cstdio>
#include<cmath>
const int N=120001,R=10000000;
int n,p,i,t,s[N],e=-1,l,f[]={1,10,100,1000,10000,100000,1000000};
typedef struct P
{
	double x,y;
};
P v[N],r,u[N];
#define A(a,b,c) ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))
char q[R];
int B()
{
  	int s=0;
  	for(e++;q[e]>='0'&&q[e]<='9';e++)
  		s=s*10+q[e]-'0';
  	return s;
}
double C()
{
    int s=1,v=-1;
    double x=0;
    for(;(q[e]<'0'||q[e]>'9')&&q[e]!='-'&&q[e]!='.';e++);
    for(;q[e]>='0'&&q[e]<='9'||q[e]=='-'||q[e]=='.';e++)
        if(q[e]=='-')
            s=-1;
        else if(q[e]=='.')
            v=0;
        else if(v==-1)
            x=x*10+q[e]-'0';
        else
            x+=1.0*(q[e]-'0')/f[++v];
    return x*s;
}
void S(int x)
{
    int i,d=x>999999999?10:x>99999999?9:x>9999999?8:x>999999?7:x>99999?6:x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,i--)
        q[l+i]=x%10+48;
    q[l+d]=10,l+=d+1;
}
void T(double x,char c)
{
    if(x<0)
        x=-x,q[l++]='-';
    int y=(int)x,e[100],f[100],j=0,k=0,i;
    int z=round((x-y)*1000000);
    for(;y;y/=10)
        e[++j]=y%10;
    if(!j)
        q[l++]=48;
    else
        for(i=j;i;i--)
            q[l++]=e[i]+48;
    for(;z;z/=10)
        f[++k]=z%10;
    q[l++]='.';
    for(i=6;i;i--)
        q[l++]=f[i]+48;
    q[l++]=c;
}
void M(int l,int r)
{
    if(l==r)
        return;
    int i,j,k,m=(l+r)/2;
    for(M(l,m),M(m+1,r),i=k=l,j=m+1;i<=m||j<=r;)
    	u[k++]=(j>r||(i<=m&&A(v[1],v[i],v[j])<0))?v[i++]:v[j++];
    for(i=l;i<=r;i++)
        v[i]=u[i];
}
int main()
{
    freopen("infasuratoare.in","r",stdin),freopen("infasuratoare.out","w",stdout),fread(q,1,R,stdin),n=B();
    for(p=i=1;i<=n;i++)
        v[i].x=C(),v[i].y=C(),p=v[i].x<v[p].x||(v[i].x==v[p].x&&v[i].y<v[p].y)?i:p;
    for(r=v[1],v[1]=v[p],v[p]=r,M(2,n),s[++t]=1,i=2;i<=n;i++)
	{
        for(;t>1&&A(v[s[t-1]],v[s[t]],v[i])>0;t--);
        s[++t]=i;
    }
    for(S(t);t;t--)
        T(v[s[t]].x,' '),T(v[s[t]].y,'\n');
    fwrite(q,1,l,stdout);
}