Cod sursa(job #2132117)

Utilizator Y.MalmsteenB.P.M. Y.Malmsteen Data 15 februarie 2018 14:25:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;
const double EPS = 1e-12;
const int Nmax = 120001;

struct punct
{
    double x, y;
};

int N, H;
punct P[Nmax];
int St[Nmax];
bool viz[Nmax];

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

double det(const punct &A, const punct &B, const punct &C)
{
    return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}

bool compx(const punct &A, const punct &B)
{
    if(A.x == B.x) return A.y < B.y;
    return A.x < B.x;
}

void citire()
{
    f >> N;
    for(int i = 1; i <= N; i++)
        f >> P[i].x >> P[i].y;
}

void afisare()
{
    g << H << '\n';
    g << fixed << setprecision(6);
    for(int i = 1; i <= H; i++)
        g << P[St[i]].x << ' ' << P[St[i]].y << '\n';
}

void inf_convex()
{
    sort(P + 1, P + N + 1, compx);
    St[1] = 1;
    St[2] = 2;
    H = 2;
    viz[2] = 1;
    for(int i = 3, p = 1; i >= 1; i += p)
    {
        if(viz[i]) continue;
        while(H >= 2 && det(P[St[H - 1]], P[St[H]], P[i]) < EPS)
            viz[St[H--]] = 0;
        St[++H] = i;
        viz[i] = 1;
        if(i == N)p = -1;
    }
    H--;
}

int main()
{
    citire();
    inf_convex();
    afisare();
    return 0;
}