Cod sursa(job #3299522)

Utilizator mateicrainiceanuMatei Crainiceanu mateicrainiceanu Data 7 iunie 2025 18:00:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

#define MAX_POINTS 120005

typedef struct {
    double x, y;
} Point;

Point p[MAX_POINTS];

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

int det_sign(Point a, Point b, Point c) {
    double det = a.x * b.y - b.y * c.x + b.x * c.y - c.y * a.x + c.x * a.y  - a.y * b.x;
    if (det > 0) return 1;
    if (det < 0) return -1;
    return 0;
}

int ans[MAX_POINTS];

int main() {
    int n;
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;

    sort(p + 1, p + n + 1, cmp);

    ans[++ans[0]] = 1;
    ans[++ans[0]] = 2;

    for (int i = 3; i <= n; i++) {
        int sz = ans[0];
        while (sz > 1 && det_sign(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1)
        {
            ans[0]--;
            sz = ans[0];
        }
        ans[++ans[0]] = i;
    }

    for (int i = n - 1; i >= 1; i--) {
        int sz = ans[0];

        while (sz > 1 && det_sign(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1) {
            ans[0]--;
            sz = ans[0];
        }
        ans[++ans[0]] = i;
    }

    fout << ans[0] - 1 << '\n';

    for (int i = 1; i < ans[0]; i++) {
        fout << fixed << setprecision(12) << p[ans[i]].x << " " << p[ans[i]].y << '\n';
    }

    fout.close();
    return 0;
}