Cod sursa(job #3246557)

Utilizator deerMohanu Dominic deer Data 3 octombrie 2024 17:07:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>

using namespace std;

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

const int MAX = 120005;

struct ura {
    float x, y;
} v[MAX];

int s[MAX], ns = 0, s2[MAX], ns2 = 0;

bool verif_jos(int i, int xa, int ya, int xb, int yb) {
    int xc = v[i].x, yc = v[i].y;
    return (xa * yb + xb * yc + xc * ya) < (ya * xb + yb * xc + yc * xa);
}

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

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);
    float xa = v[1].x, ya = v[1].y, xb = v[n].x, yb = v[n].y;
    s[++ns] = 1;
    for (int i = 2; i <= n; i++) {
        while (ns > 1 && verif_jos(i, v[s[ns - 1]].x, v[s[ns - 1]].y, v[s[ns]].x, v[s[ns]].y)) {
            ns--;
        }
        s[++ns] = i;
    }
    s2[++ns2] = n;
    for (int i = n - 1; i >= 1; i--) {
        while (ns2 > 1 && !verif_jos(i, v[s2[ns2 - 1]].x, v[s2[ns2 - 1]].y, v[s2[ns2]].x, v[s2[ns2]].y)) {
            ns2--;
        }
        s2[++ns2] = i;
    }

    cout << ns + ns2 - 2 << '\n';
    cout << fixed << setprecision(6);
    for (int i = 1; i <= ns; i++) {
        cout << v[s[i]].x << " " << v[s[i]].y << '\n';
    }
    for (int i = 2; i < ns2; i++) {
        cout << v[s2[i]].x << " " << v[s2[i]].y << '\n';
    }

    return 0;
}