Cod sursa(job #1809700)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 19 noiembrie 2016 10:37:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<cstdio>
#define x first
#define y second
#define eps 1e-12
#define punct pair<double,double>
#include<vector>
#include<algorithm>

using namespace std;

punct a[120003];
int s[120003],i,n,k,q;
bool fol[120003];

bool semn(punct o,punct a,punct b)
{
    return ((a.first-o.first)*(b.second-o.second)+(o.first-b.first)*(a.second-o.second)>eps);
}

bool cmp(punct a,punct b)
{
    if(a.first>b.first)
    {
        return true;
    }
    if(a.first==b.first)
    {
        return (a.second>b.second);
    }
    return false;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].first,&a[i].second);
    }
    sort(a+1,a+n+1,cmp);
    s[1]=1;
    s[2]=2;
    k=2;
    q=1;
    i=3;
    fol[2]=true;
    for(i=3;i>0;i+=q)
    {
        if(i==n)
        {
            q=-1;
        }
        while(semn(a[s[k-1]],a[s[k]],a[i])&&k>=2)
        {
            fol[s[k--]]=false;
        }
        s[++k]=i;
        fol[i]=true;
    }
    printf("%d\n",k-1);
    for(i=1;i<k;i++)
    {
        printf("%.6lf %.6lf\n",a[s[i]].first,a[s[i]].second);
    }
    return 0;
}