Cod sursa(job #2697807)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 19 ianuarie 2021 18:12:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const double EPS = 1e-9;
const int NMAX = 120002;

struct Punct
{
    double x, y;
};

int N, H;
Punct P[NMAX];
int St[NMAX];
bool viz[NMAX];

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) ///<0
            viz[St[H--]] = 0;
        St[++H] = i;
        viz[i] = 1;
        if(i == N)
            p = -1;
    }
    H--;
}

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