Cod sursa(job #3180459)

Utilizator tudor_costinCostin Tudor tudor_costin Data 5 decembrie 2023 12:03:14
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define y first
#define x second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005;
const long double eps = 1e-12;
pair<long double,long double> a[Nmax];
vector<int> st;
bool viz[Nmax];
bool isright(pair<long double,long double> c,pair<long double,long double> a,pair<long double,long double> b)
{
    return ((c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.y-a.y)>=eps);
}
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);
    st.push_back(1);
    st.push_back(2);
    viz[2]=1;
    int ind=1;
    int sgn=1;
    for(int i=3;i>0;i+=sgn)
    {
        if(i==n) sgn=-1;
        if(!viz[i])
        {
            while(ind>0 && isright(a[i],a[st[ind-1]],a[st[ind]]))
            {
                viz[st[ind]]=0;
                st.pop_back();
                ind--;
            }
            st.push_back(i);
            ind++;
            viz[i]=1;
        }
    }
    fout<<ind<<'\n';
    for(int i=0;i<ind;i++)
    {
        fout<<setprecision(12)<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
    }
    return 0;
}