Cod sursa(job #3243994)

Utilizator StefanStratonStefan StefanStraton Data 22 septembrie 2024 19:48:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.93 kb
#include <iomanip>
#include <fstream>
#include <algorithm>
#define MAX 2000000000

using namespace std;
ifstream in ("infasuratoare.in"); ofstream out ("infasuratoare.out");

int pct_st_jos, pct_dr_sus;
struct point {
    double x, y;
    int side;    // partea de sus sau jos fata de dreapta dintre pct_st_jos si pct_dr_sus
} v[120001];

int stiva[120001];

// aria triunghiului abc calculata cu determinanti pt a determina de ce parte se afla pct c fata de dreapta dintre pct_st_jos si pct_dr_sus
double Pe_ce_parte(point a, point b, point 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;
}

bool cmp(point a, point b) {
    if (a.y < b.y) return true;
    else if (a.y > b.y) return false;
    else return (a.x < b.x);
}

int main() {
    int i, n; in >> n;
    for (i = 1; i <= n; i++)in >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    pct_st_jos = 1; pct_dr_sus = n;

    // stabilesc pt fiecare pct pe ce parte fata de dreapta dintre pct_st_jos si pct_dr_sus se afla
    for (i = 1; i <= n; i++)
        if (i != pct_st_jos && i != pct_dr_sus) {
            if (Pe_ce_parte(v[pct_st_jos], v[pct_dr_sus], v[i]) < 0) v[i].side = 1;  // Partea de sus
            else v[i].side = -1; // Partea de jos
        }
    int ind;
    v[1].side = -1;  // pct_st_jos va fi pe partea inferioara
    v[n].side = 1;   // pct_dr_sus maxim va fi pe partea superioara
    stiva[1] = 1; i = 2;

    //  primul punct din partea de sus
    while (v[i].side == -1 && i < n) i++;
    stiva[2] = i; ind = 2;

    int p; double semn; p = v[stiva[2]].side;

    // rezolv partea de sus
    for (i = i + 1; i <= n; i++) {
        if (v[i].side == p) {
            semn = Pe_ce_parte(v[stiva[ind - 1]], v[stiva[ind]], v[i]);

            while (semn * v[i].side < 0 && ind > 0) {
                ind--;
                semn = Pe_ce_parte(v[stiva[ind - 1]], v[stiva[ind]], v[i]);
            }
            ind++;
            stiva[ind] = i;
        }
    }
    i = n - 1; p = -1;

    // rezolv partea de jos
    while (v[i].side == 1 && i > 1) i--;
    ind++;
    stiva[ind] = i;

    for (i = i - 1; i >= 2; i--) {
        if (v[i].side == p) {
            semn = Pe_ce_parte(v[stiva[ind - 1]], v[stiva[ind]], v[i]);

            while (semn * v[i].side > 0 && ind > 0) {
                ind--;
                semn = Pe_ce_parte(v[stiva[ind - 1]], v[stiva[ind]], v[i]);
            }
            ind++;
            stiva[ind] = i;
        }
    }

    // inchidere infasuratoare convexa
    semn = Pe_ce_parte(v[stiva[ind - 1]], v[stiva[ind]], v[1]);
    while (semn * v[1].side > 0 && ind > 0) {
        ind--;
        semn = Pe_ce_parte(v[stiva[ind - 1]], v[stiva[ind]], v[1]);
    }
    out<< ind << '\n';
    for (i = 1; i <= ind; i++)
        out << fixed << setprecision(6) << v[stiva[i]].x << " " << v[stiva[i]].y << '\n';
    in.close(); out.close();
    return 0;
}