Cod sursa(job #2339176)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 8 februarie 2019 15:35:15
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

#define eps 1e-12

using namespace std;

int n;
double x, y;
vector <pair<int,int>> pct;
vector <int> q, q1;

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>>x>>y;
        pct.push_back({x,y});
    }
    sort(pct.begin(),pct.end());

    q1.push_back(n-1);
    q1.push_back(n-2);
    for(int i=n-3;i>=0;--i){
         while(q1.size()>1 && det(q1[q1.size()-2],q1.back(),i)<eps)
            q1.pop_back();
        q1.push_back(i);
    }

    q.push_back(0);
    q.push_back(1);

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

    q.pop_back();
    q.erase(q.begin());

    cout<<q1.size()+q.size()<<"\n";

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

    for(int i : q1)
        cout<<pct[i].first<<" "<<pct[i].second<<"\n";
    return 0;
}