Cod sursa(job #2339218)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 8 februarie 2019 16:08:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#define EPSILON 1e-12

using namespace std;
vector <pair<double,double>> p;
vector <int> sol;
bitset <120005> viz;
int n;
double a,b;
double det(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
    return (b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a>>b;
        p.push_back({a,b});
    }
    sort(p.begin(),p.end());
    sol.push_back(0);
    sol.push_back(1);
    viz[1]=1;
    int l=2;
    for(int i=2;i<n;++i)
    {
        if(viz[i])
            continue;
        while(l>=2 && det(p[sol[l-2]],p[sol[l-1]],p[i])<EPSILON)
        {
            viz[sol[l-1]]=0;
            --l;
            sol.pop_back();
        }
        ++l;
        sol.push_back(i);
        viz[i]=1;
    }
    for(int i=n-1;i>=0;--i)
    {
        if(viz[i])
            continue;
        while(l>=2 && det(p[sol[l-2]],p[sol[l-1]],p[i])<EPSILON)
        {
            viz[sol[l-1]]=0;
            --l;
            sol.pop_back();
        }
        ++l;
        sol.push_back(i);
        viz[i]=1;
    }
    sol.erase(sol.begin());
    cout<<sol.size()<<"\n";
    cout<<fixed<<setprecision(6);
    for(int i:sol)
        cout<<p[i].first<<" "<<p[i].second<<"\n";
    return 0;
}