Cod sursa(job #2277423)

Utilizator EricEric Vilcu Eric Data 6 noiembrie 2018 11:04:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
const int NM=120002;
struct dot{double x,y;} a[NM];
bool tk[NM];
int n,s[NM],l;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool convex(dot A1,dot A2,dot A3)
{
    if((A2.x-A1.x)*(A3.y-A1.y)-(A2.y-A1.y)*(A3.x-A1.x)>0.000000000001)return 1;
    return 0;
}
bool mere(int i)
{
    if(convex(a[s[l-1]],a[s[l]],a[i]))return 1;
    return 0;
}
bool sa(dot A,dot B)
{
    if(A.x<B.x)return 1;
    if(A.x==B.x&&A.y<B.y)return 1;
    return 0;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;++i)f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,sa);
    s[1]=1;s[2]=2;tk[2]=1;l=2;
    for(int i=1;i<=n;++i)
    {
        if(!tk[i])
        {
            while(l>=2&&!mere(i)){tk[s[l]]=0;--l;}
            ++l;
            s[l]=i;tk[i]=1;
        }
    }
    for(int i=n;i>0;--i)
    {
        if(!tk[i])
        {
            while(l>=2&&!mere(i)){tk[s[l]]=0;--l;}
            ++l;
            s[l]=i;tk[i]=1;
        }
    }
    --l;
    g<<l<<'\n';
    g<<setprecision(6)<<fixed;
    for(int i=1;i<=l;++i)g<<a[s[i]].x<<' '<<a[s[i]].y<<'\n';
}