Cod sursa(job #3359333)

Utilizator Stamate_DavidStamate David Stamate_David Data 27 iunie 2026 10:57:12
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

typedef long double ld;

struct point {
    ld x, y;
};

point pivot;

ld cross(point o, point a, point b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

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

bool cmp(point a, point b) {
    ld cp = cross(pivot, a, b);
    if (cp != 0) return cp > 0;
    return dist2(pivot, a) < dist2(pivot, b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int n;
    cin >> n;

    vector<point> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }

    int minidx = 0;
    for (int i = 1; i < n; i++) {
        if (pts[i].x < pts[minidx].x ||
           (pts[i].x == pts[minidx].x && pts[i].y < pts[minidx].y))
            minidx = i;
    }
    swap(pts[0], pts[minidx]);
    pivot = pts[0];

    sort(pts.begin() + 1, pts.end(), cmp);

    vector<point> hull;
    hull.push_back(pts[0]);
    hull.push_back(pts[1]);

    for (int i = 2; i < n; i++) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }

    int h = hull.size();
    cout << h << "\n";
    cout << fixed << setprecision(6);
    for (int i = 0; i < h; i++) {
        cout << hull[i].x << " " << hull[i].y << "\n";
    }

    return 0;
}