Cod sursa(job #3349255)

Utilizator livliviLivia Magureanu livlivi Data 26 martie 2026 21:42:30
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
//
//  main.cpp
//  Infasuratoare convexa
//
//  Created by Andrada Minca on 25.03.2026.
//

#include <fstream>
#include <iomanip>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct{
    long double x;
    long double y;
};
vector<punct>v;
bool cmp(punct a,punct b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
long double arie(punct a,punct b,punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-c.y*a.x-b.x*a.y;
}
const long double EPS=1e-15;
int main()
{
    int n;
    cin>>n;
    v.resize(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort(v.begin(),v.end(),cmp);
    vector<int> ans;
    for(int i=0;i<n;i++)
    {
        while (ans.size()>=2&&arie(v[ans[ans.size()-2]],v[ans[ans.size()-1]],v[i]) < EPS)
        {
            ans.pop_back();
        }
        ans.push_back(i);
    }
    int t=ans.size();
    for(int i=n-2;i>=0;i--)
    {
        while(ans.size()>t&&arie(v[ans[ans.size()-2]],v[ans[ans.size()-1]],v[i]) < EPS)
        {
            ans.pop_back();
        }
        ans.push_back(i);
    }
    ans.pop_back();
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++)
    {
        cout<<setprecision(13);
        cout<<v[ans[i]].x<<" "<<v[ans[i]].y<<'\n';
        //cout<<ans[i]<<" ";
    }
    return EXIT_SUCCESS;
}