Cod sursa(job #3354660)

Utilizator coldsh1tANdrei coldsh1t Data 19 mai 2026 17:36:43
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct q
{
    double x, y;
};

q v[120005];

int cmp(q a, q b)
{
    if(a.x<b.x)
    {
        return true;
    }
    else if(a.x>b.x)
    {
        return false;
    }
    else
    {
        if(a.y<b.y)
        {
            return true;
        }
        return false;
    }
}

int arie(q a, q b, q 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;
}

q v1[120005], v2[120005], st[120005], a[120005];

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

    int cnt1=0, cnt2=0;

    for(int i=2;i<n;i++)
    {
        if(arie(v[1], v[n], v[i])>0)
        {
            cnt2++;
            v2[cnt2].x=v[i].x;
            v2[cnt2].y=v[i].y;
        }
        else
        {
            cnt1++;
            v1[cnt1].x=v[i].x;
            v1[cnt1].y=v[i].y;
        }
    }

    st[1].x=v[1].x;
    st[1].y=v[1].y;
    st[2].y=v1[2].y;
    st[2].x=v1[2].x;

    int k=2;

    for(int i=3;i<=cnt1;i++)
    {
        while(k>=2 && arie(st[k-1], st[k], v1[i])<0)
        {
            k--;
        }
        st[++k]=v1[i];
    }

    int cnt=0, ktotal=0;
    ktotal+=k;

    for(int i=1;i<=k;i++)
    {
        cnt++;
        a[cnt].x=st[i].x;
        a[cnt].y=st[i].y;
    }


    st[1].x=v[1].x;
    st[1].y=v[1].y;
    st[2].y=v2[2].y;
    st[2].x=v2[2].x;

    k=2;

    for(int i=3;i<=cnt2;i++)
    {
        while(k>=2 && arie(st[k-1], st[k], v2[i])>0)
        {
            k--;
        }
        st[++k]=v2[i];
    }

    for(int i=k;i>0;i--)
    {
        cnt++;
        a[cnt].x=st[i].x;
        a[cnt].y=st[i].y;
    }

    fout<<cnt+2<<"\n"<<v[1].x<<" "<<v[1].y<<"\n";

    for(int i=1;i<=cnt;i++)
    {
        fout<<a[i].x<<" "<<a[i].y<<"\n";
    }

    fout<<v[n].x<<" "<<v[n].y;

    return 0;
}