Cod sursa(job #2339232)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 8 februarie 2019 16:27:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iomanip>

#define eps 1e-12

using namespace std;

int n,l;
double x,y;
vector <pair<double, double>> p;
vector <int> q;
bitset <120005> viz;

double det(int p1, int p2, int p3){
    return (p[p2].first-p[p1].first) * (p[p3].second-p[p1].second) - (p[p2].second-p[p1].second) * (p[p3].first-p[p1].first);
}

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

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x>>y;
        p.push_back({x,y});
    }
    sort(p.begin(),p.end());

    q.push_back(0);
    q.push_back(1);
    viz[1]=1, l=2;

    for(int i=2;i<n;++i){
        if(viz[i])
            continue;
        while(l>1 && det(q[l-2],q[l-1],i)<eps){
            --l;
            viz[q.back()]=0;
            q.pop_back();
        }
        ++l;
        q.push_back(i);
        viz[i]=1;
    }

    for(int i=n-1;i>=0;--i){
        if(viz[i])
            continue;
        while(l>1 && det(q[l-2],q[l-1],i)<eps){
            --l;
            viz[q.back()]=0;
            q.pop_back();
        }
        ++l;
        q.push_back(i);
        viz[i]=1;
    }

    q.erase(q.begin());
    cout<<l-1<<"\n";
    cout<<fixed<<setprecision(6);
    for(int i : q)
        cout<<p[i].first<<" "<<p[i].second<<"\n";

    return 0;
}