Cod sursa(job #3349092)

Utilizator Andrada_MincaAndrada Minca Andrada_Minca Data 25 martie 2026 13:55:36
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 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{
    double x;
    double y;
};
vector<punct>v;
bool cmp(punct a,punct b)
{
    return a.x<b.x;
}
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;
}
int ok(int a,int b,int c)
{
    float aria=arie(v[a],v[b],v[c]);
    if(aria>0)return 1;
    if(aria<0)return 0;
    return -1;
}
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);
    stack<int>st;
    st.push(0);
    st.push(1);
    for(int i=2;i<n;i++)
    {
        int b=st.top();
        st.pop();
        int a=st.top();
        st.push(b);
        while(st.size()>1&&ok(a,b,i)!=0)
        {
            st.pop();
            //cout<<"nu e bine l-am scos pe "<<b<<'\n';
            if(st.size()>1)
            {
                b=st.top();
                st.pop();
                a=st.top();
                st.push(b);
            }
        }
        st.push(i);
    }
    vector<int> ans;
    while(!st.empty())
    {
        ans.push_back(st.top());
        st.pop();
    }
    for(int i=0;i<ans.size()/2;i++)
    {
        swap(ans[ans.size()-i-1],ans[i]);
    }
    st.push(0);
    st.push(1);
    for(int i=2;i<n;i++)
    {
        int b=st.top();
        st.pop();
        int a=st.top();
        st.push(b);
        while(st.size()>1&&ok(a,b,i)!=1)
        {
            st.pop();
            if(st.size()>1)
            {
                b=st.top();
                st.pop();
                a=st.top();
                st.push(b);
            }
        }
        st.push(i);
    }
    st.pop();
    while(!st.empty())
    {
        ans.push_back(st.top());
        st.pop();
    }
    ans.pop_back();
    cout<<ans.size()<<'\n';
    for(int i=ans.size()-1;i>=0;i--)
    {
        cout<<setprecision(13);
        cout<<v[ans[i]].x<<" "<<v[ans[i]].y<<'\n';
        //cout<<ans[i]<<" ";
    }
    return EXIT_SUCCESS;
}