Cod sursa(job #3002630)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 14 martie 2023 22:25:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct pct
{
    double x,y;
} a[120005];
int st[120005];
bool viz[120005];
bool cmp(pct X,pct Y)
{
    if(X.x==Y.x)
        return X.y<Y.y;
    return X.x<Y.x;
}
bool determinat(pct a,pct b, pct c)
{
    return (c.y-a.y)*(b.x-a.x)>(c.x-a.x)*(b.y-a.y);
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    int vf=2;
    viz[2]=true;
    int i=3,poz=1;
    while(viz[1]==false)
    {
        if(!viz[i])
        {
            while(vf>1&& determinat(a[st[vf-1]],a[st[vf]],a[i])&&st[vf]!=n)
                viz[st[vf]]=false,vf--;
            st[++vf]=i;
            viz[i]=true;
        }
        if(i==n)
            poz=-1;
        i+=poz;
    }
    vf--;
    g<<vf<<'\n';
    for(int i=1;i<=vf;i++)
        g<<fixed<<setprecision(9)<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
    return 0;
}