Cod sursa(job #3219295)

Utilizator Laura139Anghel Laura Laura139 Data 30 martie 2024 17:43:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct punct
{
    double long x,y;
}v[120005];

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

vector <punct> st;
punct rasp[120005];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y;
    long double S=0;
    sort(v+1,v+n+1, cmp);
    st.push_back(v[1]);
    int k=1;
    for(int i=2;i<=n;i++)
    {
        if(k>=3)
        {
            long double s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
            while(s<0 && k>2)
            {
                st.pop_back();
                s=s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
                k--;
            }
        }
        st.push_back(v[i]);
        k++;
    }
    for(int i=1;i<=k;i++)
        rasp[i]=st[i];
    st.clear();
    int ck=k;
    k=1;
    st.push_back(v[n]);
    for(int i=n-1;i>=1;i--)
    {
        if(k>=3)
        {
            long double s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
            while(s>0 && k>2)
            {
                st.pop_back();
                s=s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
                k--;
            }
        }
        st.push_back(v[i]);
        k++;
    }
    cout<<ck+k-1<<'\n';
    for(int i=1;i<ck;i++)
        cout<<rasp[i].x<<" "<<rasp[i].y<<'\n';
    for(int i=2;i<k;i++)
        cout<<st[i].x<<" "<<st[i].y<<'\n';
    return 0;
}