Cod sursa(job #3030329)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 17 martie 2023 16:55:12
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
const int NMAX=120005;

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

typedef long double ld;

ld det(ld, ld, ld, ld, ld, ld);
void infasuratoare();

struct punct
{
    ld x, y;
}v[NMAX], s[NMAX], pct;

bool cmp(punct, punct);

int n;

int main()
{
    int i;
    fin>>n;
    for(i=1; i<=n; i++) fin>>v[i].x>>v[i].y;
    infasuratoare();
    return 0;
}

void infasuratoare()
{
    int i, cnt=0, poz;
    pct.x=pct.y=1e9;
    for(i=1; i<=n; i++)
    {
        if(v[i].y<pct.y)
        {
            pct=v[i];
            poz=i;
        }
        else if(v[i].y==pct.y && v[i].x<pct.x)
        {
            pct=v[i];
            poz=i;
        }
    }
    swap(v[1], v[poz]);
    sort(v+2, v+n+1, cmp);
    s[++cnt]=v[1];
    s[++cnt]=v[2];
    for(i=3; i<=n; i++)
    {
        while(cnt>=2 && det(v[i].x, v[i].y, s[cnt-1].x, s[cnt-1].y, s[cnt].x, s[cnt].y)>0)
        {
            cnt--;
        }
        s[++cnt]=v[i];
    }
    fout<<cnt<<'\n';
    for(i=cnt; i>=1; i--) fout<<fixed<<setprecision(10)<<s[i].x<<' '<<s[i].y<<'\n';
}

bool cmp(punct a, punct b)
{
    return(det(b.x, b.y, v[1].x, v[1].y, a.x, a.y)<0);
}

ld det(ld x3, ld y3, ld x1, ld y1, ld x2, ld y2)
{
    return x1*(y2-y3)-y1*(x2-x3)+(x2*y3-y2*x3);
}