Cod sursa(job #2527164)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 19 ianuarie 2020 18:54:37
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 1000000010

using namespace std;

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

int n, i, poz, k, stv[130000];
double minx, miny;

/*
    Ideea este sa sortam toate punctele dupa punctul cel mai mic ( dupa x si apoi dupa y)

    Le sortam in functie de  fata de punctul cel mai mic
*/

struct coord
{
    double x, y;
};

coord v[130000],aux;

int scoate(double x1, double y1, double x2, double y2, double x3, double y3)
{

    long double x = ((long double)x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);

    if(x >= 0)
        return 1; // sens trigonometric sau coliniar

    return 0;
}

int cmp(coord a, coord b)
{
    return (a.x * b.y) > (a.y * b.x);
}

int main()
{

    cin >> n;

    minx = INF;
    miny = INF;

    v[0].x = INF;
    v[0].y = INF;
    poz = 0;

    for(i = 1 ; i <= n; i++) // il gasim pe cel mai mic, dupa x si dupa y
    {
        cin >> v[i].x >> v[i].y;

        if(v[i].x < v[poz].x)
            poz = i;

        else if(v[i].x == v[poz].x && v[i].y < v[poz].y)
                poz = i;

    }

    aux = v[poz], v[poz] = v[1], v[1] = aux; // spunem ca e primul

    minx = v[1].x;
    miny = v[1].y;

    for(i=1 ; i <= n ; i++ )
        v[i].x -= minx, v[i].y -= miny; // scadem din toate minim, ca sa avem valori mai mici, asa e mai usor


    sort(v + 2, v + n + 1, cmp); // sortam dupa



    stv[1] = 1; // punem un numar in stiva
    stv[2] = 2;
    k = 2;

    for(i=3; i<=n; i++)
    {

while( k>=2 &&
scoate( v[i].x, v[i].y,  v[stv[k]].x, v[stv[k]].y, v[stv[k-1]].x, v[stv[k-1]].y) )
            k--; // scoatem cat timp

        stv[++k] = i;
    }

    cout << k << '\n';

    cout << fixed;

    for(i=1; i<= k; i++)
        cout << setprecision(6) << v[stv[i]].x + minx << ' ' <<
         v[stv[i]].y + miny << '\n'; // adaugam minimul la final

    return 0;
}