Cod sursa(job #2305456)

Utilizator 12222Fendt 1000 Vario 12222 Data 20 decembrie 2018 12:13:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax=120005;

int n,top;
int st[Nmax];
bitset<Nmax>viz;

struct el
{
    double x,y;

    bool operator <(const el &e)const
    {
        if(y==e.y)return x<e.x;
        return y<e.y;
    }

}a[Nmax];

inline double Semn(int A,int B,int pct)
{
    return a[pct].x*(a[A].y-a[B].y)+a[pct].y*(a[B].x-a[A].x)+a[A].x*a[B].y-a[A].y*a[B].x;
}

int main()
{
    fin>>n;

    for(int i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;

    sort(a+1,a+n+1);

    st[1]=1;
    st[2]=2;
    viz[2]=1;

    for(int i=3;i<=n;i++)
    {
        while(top>=2 && Semn(st[top],st[top-1],i)<0)
        {
            viz[st[top]]=0;
            top--;
        }
        st[++top]=i;
        viz[i]=1;
    }

    for(int i=n-1;i>=1;i--)
        if(!viz[i])
        {
            while(top>=2 && Semn(st[top],st[top-1],i)<0)
            {
                viz[st[top]]=0;
                top--;
            }
            st[++top]=i;
            viz[i]=1;
        }

    fout<<top<<"\n";

    fout<<fixed<<setprecision(12);
    for(int i=1;i<=top;i++)
        fout<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";

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