Cod sursa(job #2287614)

Utilizator bogdanbenteaBentea Bogdan bogdanbentea Data 22 noiembrie 2018 09:37:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <iostream>
using namespace std;

#define pp pair<double, double>
#define x first
#define y second

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

pp p[120010];
unsigned long long n,st[120010];

double determinant(pp a, pp b, pp c)
{
    double ans;
    ans = a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - c.y*a.x - a.y*b.x;
    return ans;
}

int main()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>p[i].x>>p[i].y;
    }
    sort(p+1,p+n+1);

    st[0]=2; ///varful stivei
    st[1]=1;
    st[2]=2;
    for(i=3;i<=n;i++)
    {
        while(st[0]>1 && determinant(p[st[st[0]-1]], p[st[st[0]]], p[i]) > 0)
            st[0]--;
        st[++st[0]]=i;
    }
    for(i=n-1;i>=1;i--)
    {
        while(determinant(p[st[st[0]-1]], p[st[st[0]]], p[i]) > 0)
            st[0]--;
        st[++st[0]]=i;
    }

    ///for(i=1;i<=st[0]-1;i++)
        ///cout<<p[st[i]].x<<" "<<p[st[i]].y<<'\n';

    fout<<st[0]-1<<'\n';
    for(i=st[0]-1;i>=1;i--)
        fout<<setprecision(6)<<fixed<<p[st[i]].x<<" "<<p[st[i]].y<<'\n';

    return 0;
}