Cod sursa(job #3246140)

Utilizator deerMohanu Dominic deer Data 1 octombrie 2024 23:15:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <bits/stdc++.h>

#define int long long

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;
using pdd = std::pair<double, double>;

using namespace std;

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

double arie(pdd a, pdd b, pdd c) {
    return a.first * b.second + b.first * c.second + c.first * a.second
         - b.second * c.first - c.second * a.first - a.second * b.first;
}

ofstream& operator << (ofstream& iesire, pdd& a) {
    iesire << a.first << " " << a.second << '\n';
    return iesire;
}

bool cmp(pdd a, pdd b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second < b.second;
}

void solve_testcase() {
    int n;
    fin >> n;
    vector<pdd> p(n);
    vi tip(n, 0);

    for (auto &it : p)
        fin >> it.first >> it.second;

    sort(all(p), cmp);

    for (int i = 1; i < n - 1; ++i) {
        if (arie(p[0], p.back(), p[i]) < 0)
            tip[i] = 1; // Point is below the line from p[0] to p.back()
        if (arie(p.front(), p.back(), p[i]) > 0)
            tip[i] = 2; // Point is above the line from p[0] to p.back()
    }

    vector<pdd> stk = {p.front()};

    // Lower hull
    for (int i = 1; i < n; ++i) {
        if (tip[i] != 2) { // Points not above
            while (stk.size() > 1 && arie(stk[stk.size() - 2], stk.back(), p[i]) < 0)
                stk.pop_back(); // Maintain convexity
            stk.push_back(p[i]);
        }
    }

    int csz = stk.size(); // Save current size of stack (lower hull)

    // Upper hull
    for (int i = n - 2; i >= 0; --i) {
        if (tip[i] != 1) { // Points not below
            while (stk.size() > csz && arie(stk[stk.size() - 2], stk.back(), p[i]) < 0)
                stk.pop_back(); // Maintain convexity
            stk.push_back(p[i]);
        }
    }

    stk.pop_back(); // Remove last point since it will be duplicated

    fout << stk.size() << '\n';
    fout << fixed << setprecision(6);

    for (auto &it : stk)
        fout << it;
}

signed main() {
    int t = 1;
    // cin >> t;
    while (t--)
        solve_testcase();
    return 0;
}