Cod sursa(job #3355765)

Utilizator lauraaaaBanaru Laura lauraaaa Data 25 mai 2026 22:49:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
    double x,y;
    int parte;
};
ura v[120001];
bool cmp (ura a,ura b)
{
    if (a.x<b.x) return true;
    else if (a.x>b.x) return false;

    if (a.y<b.y) return true;
    else return false;

    return false;
}
double pozitie (ura a,ura b, ura c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
int st[120001];
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);
    //linie
    for (i=2; i<n; i++)
    {
        double x=pozitie(v[1],v[n],v[i]);
        if (x<0) v[i].parte=1;
        else if (x>0) v[i].parte=2;
    }
    //in josul liniei
    st[1]=1;
    int k=1;
    for (i=2; i<=n; i++)
    {
        if (v[i].parte==1 || v[i].parte==0)
        {
            while (k>1 && pozitie(v[st[k-1]],v[st[k]],v[i])<0)
            {
                k--;
            }
            k++;
            st[k]=i;
        }
    }
    //in susul liniei
    int kprim=k;
    st[k]=n;
    for (i=n-1; i>=1; i--)
    {
        if (v[i].parte==2 || v[i].parte==0)
        {
            while(k>kprim && pozitie(v[st[k-1]],v[st[k]],v[i])<0)
                k--;
            k++;
            st[k]=i;
        }
    }
    cout << k-1 << endl;
    for(i=1; i<k; i++)
    {
        cout<<fixed<<setprecision(6)<< v[st[i]].x <<" "<< v[st[i]].y << '\n';
    }
    return 0;
}