Cod sursa(job #2357715)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 27 februarie 2019 17:49:23
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>

#define eps 1e-12

using namespace std;

vector <pair<double,double>> pct;
int n,s=2;
float x,y;
bitset <120005> viz;
vector <int> q;

float 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);

    scanf("%d", &n);

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

    sort(pct.begin(),pct.end());

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

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

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

    q.erase(q.begin());
    cout<<q.size()<<"\n";
    for(int i : q)
        cout<<pct[i].first<<" "<<pct[i].second<<"\n";

    return 0;
}