Cod sursa(job #3330425)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 19 decembrie 2025 15:19:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare");

struct Point
{
    double x, y;
    bool operator < (const Point &other) const
    {
        if(x != other.x)
            return (x < other.x);
        return (y < other.y);
    }
};

double cross_product(Point O, Point A, Point B)
{
    return ((A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x));
}

vector<Point> convex_hull(vector<Point> &points)
{
    vector<Point> hull;
    sort(points.begin(), points.end());
    for(auto &P : points)
    {
        while(hull.size() >= 2 && cross_product(hull[hull.size() - 2], hull.back(), P) < 0)
            hull.pop_back();
        hull.push_back(P);
    }
    int lower_size = hull.size();
    reverse(points.begin(), points.end());
    for(auto &P : points)
    {
        while(hull.size() > lower_size && cross_product(hull[hull.size() - 2], hull.back(), P) < 0)
            hull.pop_back();
        hull.push_back(P);
    }
    hull.pop_back();
    return hull;
}

int main()
{
    int n;
    fin >> n;
    vector<Point> points(n);
    for(int i = 0; i < n; i++)
        fin >> points[i].x >> points[i].y;
    vector<Point> hull = convex_hull(points);
    fout << hull.size() << "\n";
    for(auto &P : hull)
        fout << fixed << setprecision(12) << P.x << " " << P.y << "\n";

    fin.close();
    fout.close();
    return 0;
}