Cod sursa(job #1595026)

Utilizator T.C.11Tolan Cristian T.C.11 Data 9 februarie 2016 21:29:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

pair <double,double> v[120001],st[120001];
int n,i,k,Min;

bool determ(pair<double, double> A, pair<double,double> B, pair<double, double> C)
{
    if (A.first*B.second + B.first*C.second + A.second*C.first - C.first*B.second - A.first*C.second - A.second*B.first > 0)
        return true;
    else
        return false;
}

int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
    {
        fin>>v[i].first>>v[i].second;
    }
    sort(v+1,v+1+n);
    st[1]=v[1];
    st[2]=v[2];
    k=2;
    for (i=3;i<=n;i++)
    {
        while (k>1 && !determ(st[k-1],st[k],v[i]))
            k--;
        k++;
        st[k]=v[i];
    }
    Min=k;
    for (i=n-1;i>=1;i--)
    {
        while (k>Min && !determ(st[k-1],st[k],v[i]))
            k--;
        k++;
        st[k]=v[i];
    }
    fout<<k-1<<"\n";
    fout<<setprecision(6)<<fixed;
    for (i=1;i<k;i++)
    {
        fout<<st[i].first<<" "<<st[i].second<<"\n";
    }
    return 0;
}