Cod sursa(job #3030314)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 17 martie 2023 16:48:56
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 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;
    bool operator<(const punct& other) const
    {
        if(det(0, 0, x, y, other.x, other.y)==0) return x<other.x;
        return (det(0, 0, x, y, other.x, other.y)<0);
    }
}v[NMAX], s[NMAX];

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;
    sort(v+1, v+n+1);
    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';
}

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