Cod sursa(job #2535685)

Utilizator ianiIani Biro iani Data 1 februarie 2020 10:30:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

vector< pair<double,double> > puncte;
vector< pair<double,double> > steve;

double determinant(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
    return (a.first-c.first)*(b.second-c.second)-(a.second-c.second)*(b.first-c.first);
}

int n;

int main()
{
    fin>>n;
    for (int i=1;i<=n;i++)
    {
        double x,y;
        fin>>x>>y;
        puncte.push_back(make_pair(x, y));
    }
    sort(puncte.begin(), puncte.end());
    /*for (int i=0;i<n;i++)
        cout<<puncte[i].first<<' '<<puncte[i].second<<'\n';
    cout<<'\n';*/
    steve.push_back(puncte[0]);
    steve.push_back(puncte[1]);
    for (int i=2;i<n;i++)
    {
        steve.push_back(puncte[i]);
        int j=steve.size()-1;
        while (j>2&&determinant(steve[j], steve[j-1], steve[j-2])<0)
        {
            steve[j-1]=steve[j];
            j--;
            steve.pop_back();
        }
    }
    for (int i=n-2;i>=0;i--)
    {
        steve.push_back(puncte[i]);
        int j=steve.size()-1;
        while (j>2&&determinant(steve[j], steve[j-1], steve[j-2])<0)
        {
            steve[j-1]=steve[j];
            j--;
            steve.pop_back();
        }
    }
    steve.pop_back();
    fout<<steve.size()<<'\n';
    for (auto& yee:steve)
        fout<<setprecision(6)<<fixed<<yee.first<<' '<<yee.second<<'\n';
    return 0;
}