Cod sursa(job #1457103)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 iulie 2015 18:00:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

#define pdd pair<double,double>

using namespace std;

vector<pdd> P;

void Read()
{
    double x,y;
    int N;
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i){
        scanf("%lf%lf",&x,&y);
        P.push_back({x,y});
    }
    sort(P.begin(),P.end());
}

const bool broken(pdd A, pdd B, pdd C)
{
    return (B.first - A.first)*(C.second - A.second) -
            (B.second - A.second)*(C.first - A.first) > 0;
}

void Andrew_Hull()
{
    vector<pdd> Up,Dw;
    int vfu = 0,vfd = 0;
    for(auto it : P){
        while(vfu >= 2 && broken(Up[vfu-1],Up[vfu-2],it))
            Up.pop_back(),--vfu;
        while(vfd >= 2 && broken(Dw[vfd-2],Dw[vfd-1],it))
            Dw.pop_back(),--vfd;
        Up.push_back(it);++vfu;
        Dw.push_back(it);++vfd;
    }
    printf("%d\n",(int)Up.size() + (int)Dw.size() - 2);
    for(int i = 0; i < (int)Up.size()-1; ++i)
        printf("%f %f\n",Up[i].first,Up[i].second);
    for(int i = (int)Dw.size()-1; i >= 1; --i)
        printf("%f %f\n",Dw[i].first,Dw[i].second);

}

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

    Read();
    Andrew_Hull();

    return 0;
}