Cod sursa(job #3353328)

Utilizator dubitDarius Dubit dubit Data 6 mai 2026 10:38:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 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) // Determinantul (produs vectorial). Semnul indica orientarea
{                                   // >0 viraj la stanga; <0 viraj la dreapta; =0 coliniar
    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 // Cautam punctul minim (cel mai jos si la stanga)
               || (v[i].y==v[minimizedpoint].y && v[i].x<v[minimizedpoint].x) )
                    minimizedpoint=i;
        }

    v[0]=v[minimizedpoint]; // In v[0] am retine offset-ul de la minim la origine, dar in problema asta nu am avut nevoie.
    swap(v[minimizedpoint],v[1]); //Interschimbam punctul minim cu primul punct
    origin=v[1];

    sort(v+2,v+n+1,cmp); // Sortam trigonometric

    int firstDetNotEqualToZero;
    for(firstDetNotEqualToZero=2;firstDetNotEqualToZero<=n;firstDetNotEqualToZero++) // Gasim primul punct necoliniar
        if(det(v[1],v[2],v[firstDetNotEqualToZero]))
            break;

    for(int i=2, j=firstDetNotEqualToZero-1;i<j;i++,j--) //Inversam punctele coliniare cele mai apropiate de pivot pt scanare corecta
        swap(v[i],v[j]);

    point stk[120005]; // Stiva de puncte pentru determinarea infasuratoarei convexe
    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) // Scoatem punctele care produc viraj la dreapta (strica convexitatea)
            top--;
        stk[++top]=v[i]; // Adaugam ultimul punct la infasuratoare
    }

    cout<<top<<'\n';
    for(int i=1;i<=top;i++) // Afisam punctele infasuratoarei cu precizia specificata in enunt
        cout<<fixed<<setprecision(6)<<stk[i].x<<' '<<stk[i].y<<'\n';
    return 0;
}