Cod sursa(job #2552416)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 20 februarie 2020 20:24:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>

using namespace std;

int n;

struct Punct
{
    double x,y;
}v[120005];

bool cmp(Punct a, Punct b)
{
    if(a.x>b.x)
        return false;
    else if(a.x<b.x)
        return true;
    else if(a.y>b.y)
        return false;
    return true;
}

Punct stjos[120005],stsus[120005];

double arie(Punct a, Punct b, Punct c)
{
    /// x1 y1 1 ///a
    /// x2 y2 1 ///b
    /// x3 y3 1 ///c
    double arie=a.x*(b.y-c.y)-b.x*(a.y-c.y)+c.x*(a.y-b.y);
    return arie;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin>>n;
    int i,vfjos,vfsus;
    for(i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    stjos[1]=v[1];
    vfjos=1;
    stsus[1]=v[1];
    vfsus=1;
    for(i=2;i<=n;i++){
        if(arie(v[1],v[n],v[i])<=0)///jos
        {
            while(vfjos>1 && arie(stjos[vfjos-1],stjos[vfjos],v[i])<0)
                vfjos--;
            stjos[++vfjos]=v[i];
        }
        if(arie(v[1],v[n],v[i])>=0)
        {
            while(vfsus>1 && arie(stsus[vfsus-1],stsus[vfsus],v[i])>0)
                vfsus--;
            stsus[++vfsus]=v[i];
        }
    }
    cout<<vfjos+vfsus-2<<'\n';
    for(i=2;i<=vfjos;i++)
        cout<<fixed<<setprecision(6)<<stjos[i].x<<' '<<stjos[i].y<<'\n';
    for(i=vfsus-1;i>=2;i--)
        cout<<fixed<<setprecision(6)<<stsus[i].x<<' '<<stsus[i].y<<'\n';
    cout<<fixed<<setprecision(6)<<stjos[1].x<<' '<<stjos[1].y;
    return 0;
}