Cod sursa(job #3355107)

Utilizator 4CoinRicoshetJohn Doe 4CoinRicoshet Data 21 mai 2026 19:24:07
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;

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

const int GMAN = 120005;
const double eps = 1.e-12;

struct point {
    double x, y;
};

point a[GMAN];
point ll;
stack<point> st;

double cp(point P1, point P2, point P3) {
    return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}

int ccw(point P1, point P2, point P3) {

    double product;
    product = cp(P1, P2, P3);
    if (fabs(product) < eps)
        return 0;
    if (product > eps)
        return 1;
    return -1;
}

bool cmp(point a, point b) {

    if (ccw(ll, a, b) == -1)
        return 0;
    return 1;
}

int main(){

    O << fixed << showpoint << setprecision(6);
    
    int n;
    point temmie;
    I >> n;
    I >> temmie.x >> temmie.y;
    a[1] = temmie;
    for (int i = 2; i <= n; i++) {

        I >> temmie.x >> temmie.y;
        if (fabs(a[1].y - temmie.y) < eps) {
            if (a[1].x - temmie.x >= eps) {
                a[i] = a[1];
                a[1] = temmie;
                continue;
            }
        }

        if (a[1].y - temmie.y >= eps) {
            a[i] = a[1];
            a[1] = temmie;
            continue;
        }

        a[i] = temmie;

    }

    ll = a[1];
    sort(a + 2, a + n + 1, cmp);

    //for (int i = 1; i <= n; i++) {
    //    O << a[i].x << ' ' << a[i].y << '\n';
    //}
    //O << '\n';

    st.push(ll);
    st.push(a[2]);

    point l = ll, ler = a[2];

    a[n + 1] = ll;

    for (int i = 3; i <= n+1; i++) {

        point tem = a[i];
        int t = ccw(l, ler, tem);
        switch (t) {
        case -1:

            st.pop();
            ler = st.top();
            st.pop();
            l = st.top();
            st.push(ler);
            i--;
            break;

        case 1:

            st.push(tem);
            l = ler;
            ler = tem;
            break;
        }

        

    }

    st.pop();
    stack<point> temst;

    while (!st.empty()) {
        temst.push(st.top());
        st.pop();
    }

    while (!temst.empty()) {
        O << temst.top().x << ' ' << temst.top().y << '\n';
        temst.pop();
    }

    return 0;

}