Cod sursa(job #1532303)

Utilizator delta_wolfAndrei Stoica delta_wolf Data 21 noiembrie 2015 15:20:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,nr,st[120009],ap[120009];

struct str
{
    double x,y;
}
pct[120009];

double EPS=0.000000000001;

double mod(double x)
{
    if(x<0) return -x;
    return x;
}

bool egal(double x,double y)
{
    return (mod(x-y)<=EPS);
}

bool cmp(str a,str b)
{
    if(egal(a.x,b.x)) return a.y<b.y;
    return a.x<b.x;
}

double det(str A,str B,str C)
{
    return (double)A.x*B.y+B.x*C.y+C.x*A.y-A.x*C.y-B.x*A.y-C.x*B.y;
}

void elim(int i)
{
    while(nr>=2&&det(pct[st[nr-1]],pct[st[nr]],pct[i])<EPS)
    {
        ap[st[nr]]=0;
        nr--;
    }
}


int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
    scanf("%lf",&pct[i].x);
    scanf("%lf",&pct[i].y);
}

sort(pct+1,pct+n+1,cmp);

nr=2;
st[1]=1;
st[2]=2;
ap[2]=1;
for(i=3;i<=n;i++)
if(ap[i]==0)
{
    elim(i);
    nr++;
    st[nr]=i;
    ap[i]=1;
}
for(i=n;i>1;i--)
    if(ap[i]==0)
    {
        elim(i);
        nr++;
        st[nr]=i;
        ap[i]=1;
    }
elim(1);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
    printf("%.6lf %.6lf\n",pct[st[i]].x,pct[st[i]].y);
return 0;
}