Cod sursa(job #3140671)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 8 iulie 2023 15:22:47
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <bitset>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct el
{
    long double x,y;
};
el v[120001];
long double d,xa,xb,xc,ya,yb,yc;
int n,i,k,stiva[120003];
bitset <120001> viz;
int cmp (const el &a,const el &b)
{
    if (a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int f (int k,int i)
{
    if (k<2)
        return 0;
    xa=v[stiva[k-1]].x;
    ya=v[stiva[k-1]].y;
    xb=v[stiva[k]].x;
    yb=v[stiva[k]].y;
    xc=v[i].x;
    yc=v[i].y;
    d=(yc-ya)*(xb-xa)-(yb-ya)*(xc-xa);
    if (d<0)
        return 1;
    else
        return 0;
}
int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;
    sort (v+1,v+n+1,cmp);
    stiva[++k]=1;
    for (i=2; i<=n; i++)
    {
        if (viz[i]==1)
            continue;
        while (k>2&&f (k,i)==1)
        {
            viz[stiva[k]]=0;
            k--;
        }
        stiva[++k]=i;
        viz[i]=1;
    }
    for (i=n-1; i>0; i--)
    {
        if (viz[i]==1)
            continue;
        while (k>2&&f (k,i)==1)
        {
            viz[stiva[k]]=0;
            k--;
        }
        stiva[++k]=i;
        viz[i]=1;
    }
    fout<<k-1<<"\n";
    for (i=1; i<k; i++)
        fout<<fixed<<setprecision (6)<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<"\n";
    return 0;
}