Cod sursa(job #2544017)

Utilizator Rares31100Popa Rares Rares31100 Data 11 februarie 2020 18:24:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define PDD pair<double,double>
#define X first
#define Y second

using namespace std;

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

int n;
PDD a[120001];
int Up[120001],vfU;
int Down[120001],vfD;

int panta(PDD a,PDD b,PDD c)
{
    double m1=(b.Y-a.Y)/(b.X-a.X);
    double m2=(c.Y-b.Y)/(c.X-b.X);

    if(m1>m2)
        return -1;
    else
        return 1;
}

int main()
{
    in>>n;

    for(int i=1;i<=n;i++)
        in>>a[i].X>>a[i].Y;

    sort(a+1,a+1+n);

    Up[1]=1;Up[2]=2;vfU=2;
    for(int i=3;i<=n;i++)
    {
        while( vfU>=2 && panta( a[ Up[ vfU-1 ] ], a[ Up[ vfU ] ], a[i])>0 )
            vfU--;

        Up[++vfU]=i;
    }

    Down[1]=1;Down[2]=2;vfD=2;
    for(int i=3;i<=n;i++)
    {
        while( vfD>=2 && panta( a[ Down[ vfD-1 ] ], a[ Down[ vfD ] ], a[i])<0 )
            vfD--;

        Down[++vfD]=i;
    }

    out<<vfU+vfD-2<<'\n';

    for(int i=vfU;i>=1;i--)
        out<<setprecision(6)<<fixed<<a[ Up[i] ].X<<' '<<a[ Up[i] ].Y<<'\n';

    for(int i=2;i<=vfD-1;i++)
        out<<a[ Down[i] ].X<<' '<<a[ Down[i] ].Y<<'\n';

    return 0;
}