Cod sursa(job #3220159)

Utilizator Sasha_12454Sasha Costea Sasha_12454 Data 2 aprilie 2024 17:27:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
const int NMAX=120005;
int n;
int ind;
int leftmax=1e9+1;
int ymin;
int saiz;
struct punct
{
    long double x,y;
};
punct v[NMAX],st[NMAX];
inline double cross_product(punct origine,punct A, punct B)
{
    return (A.x-origine.x)*(B.y-origine.y)-(A.y-origine.y)*(B.x-origine.x);
}
bool cmp(punct A, punct B)
{
    return cross_product(v[1],A,B)>0;
}
void infasuratoare_convexa()
{
    st[1]=v[1];
    st[2]=v[2];
    saiz=2;
    for(int i=3; i<=n; i++)
    {
        while(saiz>=2 && cross_product(st[saiz-1],st[saiz],v[i])<=0)
        {
            saiz--;
        }
        st[++saiz]=v[i];
    }
    out<<saiz<<'\n';
    for(int i=1; i<=saiz; i++)
    {
        out<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';
    }
}
int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>v[i].x>>v[i].y;
    }
    for(int i=1; i<=n; i++)
    {
        if(v[i].x<leftmax)
        {
            ind=i;
            leftmax=v[i].x;
            ymin=v[i].y;
     
        }
        else if(v[i].x==leftmax)
        {
            if(v[i].y<ymin)
            {
                ymin=v[i].y;
                ind=i;
            }
        }
    }
    swap(v[1],v[ind]);
    /*out<<v[1].x<<" "<<v[1].y;*/
    sort(v+2,v+n+1,cmp);
    infasuratoare_convexa();
    return 0;
}