Cod sursa(job #3277852)

Utilizator andreea0146Nicula Andreea andreea0146 Data 17 februarie 2025 15:40:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
const int NMAX=120001;

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

struct punct
{
    double x,y;
};

int n,nrp;
punct p[NMAX], st[NMAX];

double det(const punct &a,const punct &b,const punct &c)
{
    return (a.x-b.x)*(b.y-c.y)-(a.y-b.y)*(b.x-c.x);
}

bool compd(const punct &a, const punct &b)
{
    return det(p[1],a,b)>0;
}

bool compx(const punct &a, const punct &b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;

}

void citire()
{
    fin>>n;
    int pmin=1;
    for(int i=1; i<=n; i++)
    {
        fin>>p[i].x>>p[i].y;
        if(compx(p[i],p[pmin]))
            pmin=i;
    }
    swap(p[1],p[pmin]);
}

void graham()
{
    sort(p+2,p+n+1,compd);
    st[1]=p[1];
    st[2]=p[2];
    nrp=2;
    for(int i=3; i<=n; i++)
    {
        while(nrp>=2&&det(st[nrp-1],st[nrp],p[i])<0)
            nrp--;
        st[++nrp]=p[i];
    }
}

void afisare()
{
    fout<<nrp<<'\n';
    fout<<fixed<<setprecision(6);
    for(int i=1; i<=nrp; i++)
        fout<<st[i].x<<' '<<st[i].y<<'\n';
}

int main()
{
    citire();
    graham();
    afisare();

    fin.close();
    fout.close();
    return 0;
}