Cod sursa(job #3248877)

Utilizator MMEnisEnis Mutlu MMEnis Data 13 octombrie 2024 16:42:58
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

int stiva[120001];
int x1, y1, x2, y2;

struct cel
{
    double x, y;
}v[120001];

int cmp ( cel a, cel b )
{
    if ( a.x == b.x )
        return a.y < b.y;
    return a.x < b.x;
}

int arie( int xa, int ya, int xb, int yb, int xc, int yc )
{
    return xa*yb + xb*yc + xc*ya - xc*yb - xa*yc - xb*ya;
}

int main()
{
    int n, i;
    f >> n;
    for ( i = 1; i <= n; i ++ )
        f >> v[i].x >> v[i].y;
    sort ( v + 1, v + n + 1, cmp );
    x1 = v[1].x;
    y1 = v[1].y;
    x2 = v[n].x;
    y2 = v[n].y;
    int k = 1;
    stiva[k] = 1;
    for ( i = 2; i <= n; i ++ )
    {
        if ( arie ( x1, y1, x2, y2, v[i].x, v[i].y ) < 0 )
        {
            while ( k > 1 && arie ( v[stiva[k-1]].x, v[stiva[k-1]].y, v[stiva[k]].x, v[stiva[k]].y, v[i].x, v[i].y ) < 0)
                k --;
            k ++;
            stiva[k] = i;
        }
    }
    k ++;
    int ck = k;
    stiva[k] = n;
    for ( i = n - 1; i >= 1; i -- )
    {
        if ( arie ( x1, y1, x2, y2, v[i].x, v[i].y ) > 0 )
        {
            while ( k > ck && arie ( v[stiva[k-1]].x, v[stiva[k-1]].y, v[stiva[k]].x, v[stiva[k]].y, v[i].x, v[i].y ) < 0)
                k --;
            k ++;
            stiva[k] = i;
        }
    }
    g << k << '\n';
    for ( i = 2; i <= k; i ++ )
        g << fixed << setprecision(6) << v[stiva[i]].x << " " << v[stiva[i]].y << '\n';
    g << fixed << setprecision(6) << v[1].x << " " << v[1].y;
    return 0;
}