Cod sursa(job #2169793)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 14 martie 2018 17:42:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define pdd pair<long double,long double>
#define Nmax 120003
#define ld long double
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,sav;

pdd bst;
pdd P[Nmax];
vector<pdd> H;

ld area(pdd a,pdd b,pdd c){
    return a.first*b.second + a.second * c.first + b.first * c.second - a.first * c.second - a.second * b.first - b.second * c.first;
}

bool comp(pdd a,pdd b){
    return area(bst,a,b)>0;
}

int main()
{
    f>>n;
    bst = {1e9,1e9};
    for (int i=1;i<=n;i++){
        f>>P[i].first>>P[i].second;
        if ((P[i].first<bst.first) || (P[i].first == bst.first && P[i].second<bst.second)){
            sav = i;
            bst = P[i];
        }
    }

    for (int i=sav;i<n;i++) P[i] = P[i+1];
    n--;

    sort(P+1,P+n+1,comp);

    H.push_back(bst);
    for (int i=1;i<=n;i++){
        while (H.size()>=2 && area(H[H.size()-2],H.back(),P[i])<=0) H.pop_back();
        H.push_back(P[i]);
    }

    g<<H.size()<<'\n';
    for (auto it : H) g<<fixed<<setprecision(12)<<it.first<<' '<<it.second<<'\n';

    return 0;
}