Cod sursa(job #3300921)

Utilizator Bogdan-AlxDinca Bogdan-Alexandru Bogdan-Alx Data 20 iunie 2025 05:35:13
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
    double x, y;
};

double side_of_line(point a, point b, point p)
{
    return ((p.y - a.y) * (b.x - a.x)) - ((p.x - a.x) * (b.y - a.y));
}

vector<point> convex_hull(vector<point> &pts)
{
    int n = pts.size();
    vector<point> upper, lower, hull;

    if (pts.size() < 3)
    {
        return pts;
    }

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

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

    lower.pop_back();
    upper.pop_back();
    hull = lower;
    hull.insert(hull.end(), upper.begin(), upper.end());

    return hull;
}

bool cmp(point &a, point &b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.y < b.y;
}

bool is_equal(point &a, point &b)
{
    return a.x == b.x && a.y == b.y;
}

int main(void)
{

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

    int n;
    fin >> n;

    vector<point> pts;
    pts.reserve(n);

    for (int i = 0; i < n; i++)
    {
        point p;
        fin >> p.x >> p.y;
        pts.push_back(p);
    }

    sort(pts.begin(), pts.end(), cmp);
    pts.erase(unique(pts.begin(), pts.end(), is_equal), pts.end());

    vector<point> hull = convex_hull(pts);

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

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