Cod sursa(job #2165488)

Utilizator RG1999one shot RG1999 Data 13 martie 2018 12:24:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define MAX 120001
using namespace std;
int n,i,cnt,ap[MAX],q;
int stck[MAX];
struct str
{
    double x,y;
}v[MAX];
bool cmp(str a, str b)
{
    if(a.x<b.x) return 1;
    else
        if(a.x==b.x&&a.y<b.y) return 1;
    return 0;
}
double det (str a, str b, str c)
{
    if(a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-b.x*a.y<0.0) return 1;
    return 0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    stck[1]=1;
    stck[2]=2;
    ap[2]=1;
    cnt=2;
    q=1;
    i=3;
       while(!ap[1])
    {
        while(ap[i])
        {
            if(i==n)q=-1;
            i+=q;
        }
        while(cnt>=2&&!det(v[stck[cnt]],v[stck[cnt-1]],v[i]))
            ap[stck[cnt]]=0,cnt--;
        stck[++cnt]=i;
        ap[i]=1;
    }
    printf("%d\n",cnt-1);
    for(i=2;i<=cnt;i++)
        printf("%lf %lf\n",v[stck[i]].x,v[stck[i]].y);
    return 0;
}