Cod sursa(job #3353326)

Utilizator dubitDarius Dubit dubit Data 6 mai 2026 10:31:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
/*
 * author [dubit]
*/
#include <bits/stdc++.h>

using namespace std;

struct point{
    double x,y;
};
point origin={0,0};

double det(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

double dist(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

bool cmp(point a,point b)
{
    double d=det(origin,a,b);

    if(d)
        return d>0;
    return dist(origin,a)>dist(origin,b);
}

point v[120005];
int n,minimizedpoint;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    cin>>n;
    v[0]={1000000005,1000000005};

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

            if(v[i].y<v[minimizedpoint].y
               || (v[i].y==v[minimizedpoint].y && v[i].x<v[minimizedpoint].x) )
                    minimizedpoint=i;
        }

    v[0]=v[minimizedpoint];
    swap(v[minimizedpoint],v[1]);
    origin=v[1];

    sort(v+2,v+n+1,cmp);

    int firstDetNotEqualToZero;
    for(firstDetNotEqualToZero=2;firstDetNotEqualToZero<=n;firstDetNotEqualToZero++)
        if(det(v[1],v[2],v[firstDetNotEqualToZero]))
            break;

    for(int i=2, j=firstDetNotEqualToZero-1;i<j;i++,j--)
        swap(v[i],v[j]);

    point stk[120005];
    int top=2;

    stk[1]=v[1];
    stk[2]=v[2];

    for(int i=3;i<=n;i++)
    {
        while(top>=2 && det(stk[top-1],stk[top],v[i])<0)
            top--;
        stk[++top]=v[i];
    }

    cout<<top<<'\n';
    for(int i=1;i<=top;i++)
        cout<<fixed<<setprecision(6)<<stk[i].x<<' '<<stk[i].y<<'\n';
    return 0;
}