Cod sursa(job #2000045)

Utilizator Alex18maiAlex Enache Alex18mai Data 12 iulie 2017 15:50:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

pair<double, double> A[120005];
int under[120005];
int top[120005];
bool used[120005];

double det(pair<double, double> a1, pair<double, double> a2, pair<double, double> a3){
    return a1.first*a2.second + a2.first*a3.second + a3.first*a1.second - a2.second*a3.first - a3.second*a1.first - a1.second*a2.first;
}

int main()
{
    int n;
    cin>>n;
    for ( int i=1; i<=n; i++ ){
        double x, y;
        cin>>x;
        cin>>y;
        A[i].first=x;
        A[i].second=y;
    }
    sort(A+1, A+n+1);
    int contdown=0;
    int last, beflast;
    for (int i=1; i<=n; i++){
        if (contdown > 1){
            while (contdown > 1 && det(A[beflast], A[last], A[i])> 0){
                contdown--;
                used[last]=0;
                last=under[contdown];
                beflast=under[contdown-1];
            }
        }
        contdown++;
        under[contdown]=i;
        beflast=last;
        last=i;
        if (i!=1 && i!=n){
           used[i]=1;
        }
    }
    int contup=0;
    for (int i=n; i>=1; i--){
        if (used[i] == 1){
            continue;
        }
        if (contup > 1){
            while (contup > 1 && det(A[beflast], A[last], A[i])> 0){
                contup--;
                last=top[contup];
                beflast=top[contup-1];
            }
        }
        contup++;
        top[contup]=i;
        beflast=last;
        last=i;
    }
    cout<<contdown+contup-2<<'\n';
    for (int i=contup; i>=1; i--){
        cout<<setprecision(6)<<fixed<<A[top[i]].first<<" "<<A[top[i]].second<<'\n';
    }
    for (int i=contdown-1; i>1; i--){
        cout<<setprecision(6)<<fixed<<A[under[i]].first<<" "<<A[under[i]].second<<'\n';
    }
    return 0;
}