Cod sursa(job #2060408)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 8 noiembrie 2017 10:49:46
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <bitset>
#define nman 120002
using namespace std;

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

struct duet{
    double y,x;
}v[nman];

bool cmp(duet A,duet B)
{
    return A.y<B.y;
}

int s[nman];
int n;
bitset <nman> viz;

int determinant(duet a,duet b,duet c)
{
    return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.y*b.x-c.y*a.x;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    viz[2]=1;
    int i=3;
    int dpl=1;
    int k=2;
    while(viz[1]==0)
    {
        while(viz[i]==1)
        {
            if(i==n)
            {
                dpl=-1;
            }
            i+=dpl;
        }
        while(k>=2&&determinant(v[s[k]],v[s[k-1]],v[i])<0)
        {
            viz[s[k]]=0;
            k--;
        }
        viz[i]=1;
        s[++k]=i;
    }
    fout<<k-1;
    fout<<"\n";
    for(int i=k;i>=2;i--)
    {
        fout<<setprecision(6)<<fixed;
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
    }
    return 0;
}