Cod sursa(job #2416519)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 27 aprilie 2019 17:34:47
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iomanip>

#define x first
#define y second
#define eps 1e-12

using namespace std;

pair<double,double> pct[120005];
vector <int> q;
bitset <120005> viz;
int n, len = 2;

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

}

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

    cin>>n;
    for(int i = 0; i < n; ++i)
        cin>>pct[i].first>>pct[i].second;

    sort(pct,pct+n);

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

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

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

    q.erase(q.begin());
    cout<<q.size()<<"\n";
    cout<<fixed<<setprecision(6);
    for(int i : q)
        cout<<pct[i].x<<" "<<pct[i].y<<"\n";

    return 0;
}