Cod sursa(job #2662429)

Utilizator bia_bobesBobes Bianca bia_bobes Data 24 octombrie 2020 09:05:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120005;

struct Point
{
    double x,y;
    bool operator<(const Point&other)const
    {
        if(x!=other.x)
            return x<other.x;
        return y<other.y;
    }
};
stack<int>rez;
Point v[NMAX];
bitset<NMAX>viz;
int n;
void citire()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>v[i].x>>v[i].y;
}

int det_orientare(Point a,Point b,Point c)
{
    double det=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
    if(det<0)
        return -1;
    if(det>0)
        return 1;
    return 0;
}

void solve()
{
    rez.push(0);
    viz[0]=true;
    rez.push(1);
    viz[1]=true;
    for (int i=2;i<n;i++)
    {
        int k=rez.top();
        rez.pop();
        viz[k]=false;
        while(det_orientare(v[rez.top()],v[k],v[i])>0)
        {
            k=rez.top();
            rez.pop();
            viz[k]=false;
            if(rez.empty())
                break;
        }
        rez.push(k);
        rez.push(i);
        viz[k]=viz[i]=true;
    }
    rez.pop();
    viz[n-1]=viz[0]=false;
    rez.push(n-1);
    rez.push(n-2);
    for(int i=n-3;i>=0;i--)
    {
        if(viz[i]==true)
            continue;
        int k=rez.top();
        rez.pop();
        viz[k]=false;
        while(det_orientare(v[rez.top()],v[k],v[i])>0)
        {
            k=rez.top();
            rez.pop();
            viz[k]=false;
            if(rez.empty())
                break;
        }
        rez.push(k);
        rez.push(i);
        viz[k]=viz[i]=true;
    }
}

void afish()
{
    int nr{0};
    rez.pop();
    fout<<rez.size()<<" ";
    while (!rez.empty())
    {
        int top=rez.top();
        fout<<setprecision(6)<<fixed<<v[top].x <<" "<<v[top].y <<"\n";
        rez.pop();
    }
}

int main()
{
    citire();
    sort(v,v+n);
    solve();
    afish();
    return 0;
}