Cod sursa(job #2453141)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 2 septembrie 2019 16:34:10
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define NM 120005
#define EPS 1e-12
#define point pair<double,double>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,vf,st[NM];
point v[NM];
bool viz[NM];

void Read();
void ConvexHull();
bool cmp(point,point);
int cmp1(double,double);
int ok(point,point,point);

int main()
{   Read();
    ConvexHull();
    return 0;
}

void Read()
{   f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i].x>>v[i].y;
}

void ConvexHull()
{   sort(v+1,v+n+1,cmp);
    st[1]=1;
    st[2]=2;
    viz[1]=viz[2]=true;
    vf=2;
    bool aux=false;
    for(int i=1; i; (!aux ? i++ : i--))
    {   if(i==n)
            aux=true;
        if(!viz[i])
        {   while(vf>=2 && ok(v[st[vf-1]],v[st[vf]],v[i])==-1)
                viz[st[vf--]]=false;
            st[++vf]=i;
            viz[i]=true;
        }
    }
    g<<vf-1<<'\n';
    for(int i=vf-1; i; i--)
        g<<fixed<<setprecision(6)<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}

int cmp1(double a,double b)
{   if(a+EPS<b)
        return 1;
    if(b+EPS<a)
        return -1;
    return 0;
}

bool cmp(point a,point b)
{   int ans=cmp1(a.x,b.x);
    if(ans)
        return ans==1;
    return cmp1(a.y,b.y)==1;
}

int ok(point a,point b,point c)
{   double ans=(a.x*b.y+b.x*c.y+c.x*a.y)-(c.x*b.y+a.x*c.y+b.x*a.y);
    return cmp1(ans,0);
}