Cod sursa(job #2572535)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 5 martie 2020 13:14:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include<bits/stdc++.h>
using namespace std;

inline double det(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
    return a.first*b.second+b.first*c.second+a.second*c.first-c.first*b.second-b.first*a.second-c.second*a.first;
}

const int maxN=120005;

pair<double,double> v[maxN];

bool cmp(pair<double,double> a,pair<double,double> b)
{
    return det(v[1],a,b)>0;
}

int n,p,vf;

int st[maxN];

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);

    int p=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].first,&v[i].second);

        if(v[i].first<v[p].first || (v[i].first==v[p].first && v[i].second<v[p].second)) p=i;
    }

    swap(v[1],v[p]);


    sort(v+2,v+n+1,cmp);


    st[++vf]=1;
    st[++vf]=2;

    for(int i=3;i<=n;i++)
    {
        while(vf>=2 && det(v[st[vf-1]],v[st[vf]],v[i])<0) vf--;
        st[++vf]=i;
    }

    printf("%d\n",vf);

    for(int i=1;i<=vf;i++)
        printf("%.10f %.10f\n",v[st[i]].first,v[st[i]].second);

    return 0;
}