Cod sursa(job #3345182)

Utilizator radeuojArghira Radu Stefan radeuoj Data 8 martie 2026 12:34:02
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <algorithm>

const int MAX_N = 1e5;

struct vec2 {
    double x, y;

    void read() {
        scanf("%lf %lf", &x, &y);
    }
};

struct Stack {
    int st[MAX_N];
    int sp = 0;

    int len() {
        return sp;
    }

    void push(int val) {
        st[sp++] = val;
    }

    int pop() {
        return st[--sp];
    }

    int first() {
        return st[sp - 1]; 
    }

    int second() {
        return st[sp - 2];
    }
};

int n;
vec2 a[MAX_N];

void read_points() {
    for (int i = 0; i < n; i++) {
        a[i].read();
    }
}

int find_extreme() {
    int res = 0;

    for (int i = 1; i < n; i++) {
        if (
            (a[i].y < a[res].y) ||
            (a[i].y == a[res].y && a[i].x < a[res].x)
        ) {
            res = i;
        }
    }

    return res;
}

double det(vec2 a, vec2 b, vec2 c) {
    return (c.x - a.x) * (b.y - a.y)
        - (c.y - a.y) * (b.x - a.x);
}

double dist2(vec2 a, vec2 b) {
    return (a.x - b.x) * (a.x - b.x)
        + (a.y - b.y) * (a.y - b.y);
}

void polar_sort_points() {
    vec2 a0 = a[0];

    std::sort(a + 1, a + n, [a0](vec2 a, vec2 b) {
        long long d = det(a0, a, b);

        if (d != 0) return d < 0;
        else return dist2(a0, a) < dist2(a0, b);
    });
}

Stack graham_scan() {
    Stack st;

    for (int i = 0; i < n; i++) {
        while (st.len() >= 2 && det(a[st.second()], a[st.first()], a[i]) >= 0) {
            st.pop();
        }
        st.push(i);
    }

    return st;
}

void print_hull(Stack st) {
    printf("%d\n", st.len());
    for (int i = 0; i < st.len(); i++) {
        vec2 p = a[st.st[i]];
        printf("%lf %lf\n", p.x, p.y);
    }
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &n);
    read_points();
    std::swap(a[0], a[find_extreme()]);
    polar_sort_points();
    Stack hull = graham_scan();
    print_hull(hull);
}