Cod sursa(job #3246728)

Utilizator deerMohanu Dominic deer Data 4 octombrie 2024 10:39:10
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX=120005;
struct ura
{
    double x, y;
}v[MAX];

int s[MAX], vf;

bool cmp(ura a, ura b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

bool verif_jos(int a, int b, int c)
{
    double ax=v[a].x, ay=v[a].y, bx=v[b].x, by=v[b].y, cx=v[c].x, cy=v[c].y;
    return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<0;
}

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);


    vf = 1;
    s[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(verif_jos(1, n, i))
        {
            while(vf>1 && verif_jos(s[vf-1], s[vf], i))
            {
                vf--;
            }
            s[++vf]=i;
        }
    }
    s[++vf] = n;
    int vf1=vf;

    for(int i=n - 1; i>=1; i--)
    {
        if(!verif_jos(1, n, i))
        {
            while(vf>vf1 && verif_jos(s[vf-1], s[vf], i))
            {
                vf--;
            }
            s[++vf]=i;
        }
    }
    fout<<--vf<<'\n';
    fout<<fixed<<setprecision(6);
    for(int i=1; i<=vf; i++)
    {
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
    }
    return 0;
}