Cod sursa(job #3334784)

Utilizator LucaWalucaLuca Munteanu LucaWaluca Data 19 ianuarie 2026 20:33:31
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct ura
{
    double x,y;
    int poz;
};
ura v[120005];
bool cmp(ura a, ura b)
{
    if(a.x<b.x)
        return true;
    if(a.x==b.x&&a.y<b.y)
        return true;
    return false;
}
double calc(ura a, ura b, ura c)
{
    return (a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y);
}
vector<ura> st;
signed main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for(int i=1;i<=n;i++)
        v[i].poz=(calc(v[1],v[n],v[i])>0);
    st.push_back(v[1]);
    for(int i=2;i<=n;i++)
    {
        if(v[i].poz)
            continue;
        if(st.size()==1)
            st.push_back(v[i]);
        else
        {
            while(st.size()>=2&&calc(st[st.size()-2],v[i],st[st.size()-1])>0)
                st.pop_back();
            st.push_back(v[i]);
        }
    }
    int ckc=st.size();
    v[1].poz=1;
    for(int i=n;i>=1;i--)
    {
        if(!v[i].poz)
            continue;
        if(st.size()==ckc)
            st.push_back(v[i]);
        else
        {
            while(st.size()-ckc>=1&&calc(st[st.size()-2],v[i],st[st.size()-1])>0)
                st.pop_back();
            st.push_back(v[i]);
        }
    }
    st.pop_back();
    out<<st.size()<<"\n";
    out<<fixed<<setprecision(12);
    for(int i=0;i<st.size();i++)
        out<<st[i].x<<" "<<st[i].y<<"\n";
    return 0;
}