Cod sursa(job #3224039)

Utilizator myrra678ana ana myrra678 Data 14 aprilie 2024 13:05:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct punct
{
    double x,y;
};

punct v[120001];
stack <int>st;
vector <int>r1,r2;

bool cmp(punct a,punct b)
{
    if(a.x<b.x)
        return true;
    if(a.x==b.x and a.y<b.y)
        return true;
    return false;
}

double arie(int i)
{
    double x1,x2,x3,y1,y2,y3;
    x1=v[i].x;
    y1=v[i].y;

    x2=v[st.top()].x;
    y2=v[st.top()].y;
    int aux=st.top();
    st.pop();

    x3=v[st.top()].x;
    y3=v[st.top()].y;
    st.push(aux);

    return x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);
}

int main()
{
    int n,i;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);

    for(i=1; i<=n; i++)
    {
        while(st.size()>=2 and arie(i)>0)
            st.pop();
        st.push(i);
    }
    while(!st.empty())
    {
        r1.push_back(st.top());
        st.pop();
    }


    for(i=1; i<=n; i++)
    {
        while(st.size()>=2 and arie(i)<0)
            st.pop();
        st.push(i);
    }
    while(!st.empty())
    {
        r2.push_back(st.top());
        st.pop();
    }
    reverse(r1.begin(),r1.end());

    cout<<r1.size()+r2.size()-2<<endl;

    for(i=1;i<r1.size();i++)
        cout<<fixed<<setprecision(6)<<v[r1[i]].x<<" "<<v[r1[i]].y<<'\n';
    for(i=1;i<r2.size();i++)
        cout<<fixed<<setprecision(6)<<v[r2[i]].x<<" "<<v[r2[i]].y<<'\n';
    return 0;
}