Cod sursa(job #3245816)

Utilizator eduardbuchmaneduardbuchman eduardbuchman Data 30 septembrie 2024 18:57:00
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct{
    double x, y;
    int parte;
}puncte[120005];

int st[120005];

bool cmp(punct a, punct b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

double arie(punct A, punct B, punct C) {
    return A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}

int main()
{
    int n;
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> puncte[i].x >> puncte[i].y;
    sort(puncte + 1, puncte + n + 1, cmp);
    punct jos = puncte[1];
    punct sus = puncte[n];
    for (int i = 2; i < n; i++) {
        if (arie(jos, sus, puncte[i]) < 0)
            puncte[i].parte = 1;
        else
            puncte[i].parte = 2;
    }
    int k = 1;
    st[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--;
            k++;
            st[k] = i;
        }
    int ck = k;
    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--;
            k++;
            st[k] = i;
        }
    out << k - 1 << "\n";
    for (int i = 1; i < k; i++)
        out << fixed << setprecision(6) << puncte[i].x << " " << puncte[i].y << "\n";
    return 0;
}