Cod sursa(job #3248035)

Utilizator AlexTrTrambitas Alexandru-Luca AlexTr Data 10 octombrie 2024 16:54:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMAX = 120000;

struct punct {
    double x, y;
    int parte;
} puncte[NMAX + 1];

int n, st[NMAX + 1], k, ck;

bool cmp(punct P1, punct P2)
{
    if (P1.x > P2.x)
        return false;
    if (P1.x == P2.x)
        if (P1.y > P2.y)
            return false;

    return true;
}

double arie (punct P1, punct P2, punct P3)
{
    return (P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P2.y*P3.x - P3.y*P1.x - P1.y*P2.x); /// daca <0 => P3 e sub semiplan
                                                                                    /// daca >0 => P3 e peste semiplan
}


int main()
{
    f >> n;
    for (int i = 1; i<=n; ++i)
        f >> puncte[i].x >> puncte[i].y;

    sort(puncte + 1, puncte + n + 1, cmp);

    for (int i = 2; i<=n-1; ++i)
        if (arie(puncte[1], puncte[n], puncte[i]) < 0)
            puncte[i].parte = 1;
        else
            puncte[i].parte = 2;

    st[1] = 1;
    k = 1;

    for (int i = 2; i<=n; ++i)
        if (puncte[i].parte == 1 || puncte[i].parte == 0)
        {
            while (k>1 && arie(puncte[st[k-1]], puncte[st[k]], puncte[i]) < 0)
                --k;
            st[++k] = i;
        }

    ck = k;
    st[k] = n;
    for (int i = n-1; i>=1; --i)
        if (puncte[i].parte == 2 || puncte[i].parte == 0)
        {
            while (k>ck && arie(puncte[st[k-1]], puncte[st[k]], puncte[i]) < 0)
                --k;
            st[++k] = i;
        }
    g << k-1 << '\n';
    for (int i = 1; i<=k-1; ++i)
        g << fixed <<setprecision(6) << puncte[st[i]].x << ' ' << puncte[st[i]].y << '\n';
    return 0;
}