Cod sursa(job #2156109)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 8 martie 2018 14:44:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct pct{double x;double y;};
pct v[120002],st[120002],dr[120002],sol[120002];
double aria(pct a,pct b,pct p)
{
    return a.x*(b.y-p.y)+b.x*(p.y-a.y)+p.x*(a.y-b.y);
}
bool cmp(pct a,pct b)
{
    return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,nrs=0,nrd=0,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        v[i].x+=1000000000;
        v[i].y+=1000000000;
    }
    sort(&v[1],&v[n+1],cmp);
    sol[1]=v[1];
    for(i=2;i<=n;i++)
    {
        if(aria(v[1],v[n],v[i])<=0)
            dr[++nrd]=v[i];
        else st[++nrs]=v[i];
    }
    sol[2]=dr[1];
    k=2;
    for(i=2;i<=nrd;i++)
    {
        while(aria(sol[k-1],sol[k],dr[i])<0&&k>=2)
            k--;
        sol[++k]=dr[i];
    }
    sol[++k]=st[nrs];
    for(i=nrs-1;i>=1;i--)
    {
        while(aria(sol[k],sol[k-1],st[i])>0&&k>=2)
            k--;
        sol[++k]=st[i];
    }
    while(aria(sol[k],sol[k-1],sol[1])>0&&k>=2)
        k--;
    printf("%d\n",k);
    for(i=1;i<=k;i++)
        printf("%.6lf %.6lf\n",sol[i].x-1000000000,sol[i].y-1000000000);
    return 0;
}