Cod sursa(job #3248191)

Utilizator XTrim07Florea Andrei XTrim07 Data 10 octombrie 2024 23:18:42
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int MAX_SIZE = 120000;

int stk[MAX_SIZE + 1];

struct date {
    double x, y;
    int parte; //de clarificat
} v[MAX_SIZE + 1], first, last;

bool comp(date first, date second) {
    if (first.x < second.x) {
        return true;
    }
    if (first.x > second.x) {
        return false;
    }
    if (first.y < second.y) {
        return true;
    }
    if (first.y > second.y) {
        return false;
    }
    return false;
}

double arie(date a, date b, date 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;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, comp);
    first = v[1];
    last = v[n];
    for (int i = 2; i < n; ++i) { // pana la n - 1
        if (arie(first, last, v[i]) < 0) {
            v[i].parte = 1;
        } else {
            v[i].parte = 2;
        }
    }
    stk[1] = 1;
    int k = 1;
    for (int i = 2; i <= n; ++i) {
        if (v[i].parte == 1 || v[i].parte == 0) {
            while (k > 1 && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
                --k;
            }
            ++k;
            stk[k] = i;
        }
    }
    int copy_k = k;
    stk[k] = n;
    for (int i = n - 1; i >= 1; --i) {
        if (v[i].parte == 2 || v[i].parte == 0) {
            while (k > copy_k && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
                --k;
            }
            ++k;
            stk[k] = i;
        }
    }
    fout << k - 1 << '\n';
    for (int i = 1; i < k; ++i) {
        fout << fixed << setprecision(6) << v[stk[i]].x << ' ' << v[stk[i]].y << '\n';
    }
    return 0;
}