Cod sursa(job #2284595)

Utilizator andrei2000mAndrei Moldoveanu andrei2000m Data 17 noiembrie 2018 11:49:05
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {double x,y;}a[120001];
int n,s[120001],vf;
bool sel[120001];
bool comp(punct p1,punct p2)
{
    return (p1.x<p2.x)||(p1.x==p2.x&&p1.y<p2.y);
}
double det(punct p1,punct p2,punct p3)
{
    return (p1.x*p2.y)+(p2.x*p3.y)+(p3.x*p1.y)-(p2.y*p3.x)-(p3.y*p1.x)-(p1.y*p2.x);
}
int main()
{   int i;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,comp);
    s[1]=1;vf=1;
    for(i=2;i<=n;i++)
    {
        while(vf>1&&det(a[s[vf-1]],a[s[vf]],a[i])>=0)
            {vf--;sel[s[vf+1]]=false;}
        vf++;
        s[vf]=i;
        sel[i]=true;
    }
    for(i=n;i>=1;i--)
        {
            if(sel[i]==false)
            {
                while(det(a[s[vf-1]],a[s[vf]],a[i])>=0)
                    {vf--;sel[s[vf+1]]=false;}
                vf++;
                s[vf]=i;
                sel[i]=true;
            }
        }
    g<<vf-1<<'\n';
    for(i=vf-1;i>=1;i--)
        g<<a[s[i]].x<<" "<<a[s[i]].y<<'\n';
    return 0;
}