Cod sursa(job #2174906)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 16 martie 2018 14:09:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define nmax 120002
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int viz[nmax];

struct two
{
    long double x,y;
}v[nmax];

bool cmp(two a,two b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int s[nmax];

long double det(two a,two b,two c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-c.y*a.x-a.y*b.x;
}

int main()
{
    int n;
    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 ind=1;
    int k=2;
    while(viz[1]==0)
    {
        while(viz[i]==1)
        {
            if(i==n)
                ind=-1;
            i+=ind;
        }
        while(k>=2&&det(v[s[k]],v[s[k-1]],v[i])<0)
        {
            viz[s[k]]=0;
            k--;
        }
        viz[i]=1;
        s[++k]=i;
    }
    fout<<k-1<<"\n";
    for(int i=k-1;i;i--)
    {
        fout<<fixed<<setprecision(6);
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
    }
    return 0;
}