Cod sursa(job #2869090)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 11 martie 2022 12:28:37
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.in");
struct puncte
{
    double x, y;
}punct[120020],s[120020];
double product(puncte a , puncte b , puncte c)
{
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(puncte c , puncte b)
{
    return product(punct[1] , c , b) < 0;
}
int n , vf , poz;
int main()
{
    f >> n;
    for ( int i = 1 ; i <= n ; i++)
    {
        f >> punct[i].x >> punct[i].y;
    }
    poz = 1;
    for ( int i = 2 ; i <= n ; i++)
        if( ( punct[i].x < punct[poz].x) || (punct[i].x == punct[poz].x && punct[i].y < punct[poz].y))
            poz = i;
    swap(punct[1] , punct[poz]);
    sort(punct + 2 , punct + n + 1 , cmp);
    s[1] = punct[1];
    s[2] = punct[2];
    vf = 2;
    for ( int i = 3 ; i <= n ; i++)
    {
        while( vf >= 2 && product(s[vf-1] , s[vf] , punct[i]) > 0)
            vf-- ;
        vf++;
        s[vf] = punct[i];
    }
    g << vf << '\n' ;
    for ( int i = vf ; i >= 1 ; i--)
        g << fixed << setprecision(6) << s[i].x << " " << s[i].y << '\n';
}