Cod sursa(job #3227447)

Utilizator code_blocksSpiridon Mihnea-Andrei code_blocks Data 30 aprilie 2024 16:47:45
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#include <algorithm>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

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

struct point
{
    long double x, y;

    point(long double _x = 0, long double _y = 0)
        : x(_x), y(_y) {}
} s;

// Folosit la determinarea punctului cel mai din
// stânga-jos. Apelul min_compare ar da eroare
// altfel.
bool pcompare1(point& p1, point& p2)
{
    if(p1.y != p2.y)
        return p1.y < p2.y;

    return p1.x < p2.x;
}

// Sortare trigonometrică, cerută de problemă.
// Nu se pot afișa punctele în orice ordine.
bool pcompare2(point& p1, point& p2)
{
    return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}

// p.y - s.y și p.x - s.y sunt coordonatele
// vectorului SPi, după al cărui unghi se
// sortează. Funcția atan2 dă unghiul dintre
// vectorul cu coordonatele (y, x) și abscisă.
bool acompare(point p1, point p2)
{
    long double a1 = atan2(p1.y - s.y, p1.x - s.x);
    long double a2 = atan2(p2.y - s.y, p2.x - s.x);

    return a1 < a2;
}

// Formula se deduce din coordonata pe axa Oz
// a unui produs vectorial, anume P1P2 x P1P3.
bool right(point p1, point p2, point p3)
{
    return ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) < 0;
}

vector<point> graham_scan(vector<point>& ps)
{
    s = *min_element(ps.begin(), ps.end(), pcompare1);

    sort(ps.begin(), ps.end(), acompare);

    vector<point> r;

    for(auto& p : ps)
    {
        if(r.size() >= 2)
            while(right(r[r.size() - 2], r[r.size() - 1], p))
            {
                r.pop_back();

                if(r.size() < 2)
                    break;
            }

        r.push_back(p);
    }

    sort(r.begin(), r.end(), pcompare2);

    return r;
}

int main()
{
    int n;

    vector<point> ps;

    fin >> n;

    for(int i = 1; i <= n; i++)
    {
        long double x, y;
        fin >> x >> y;
        ps.push_back(point(x, y));
    }

    vector<point> result = graham_scan(ps);

    fout << result.size() << '\n';

    for(const auto& p : result)
        fout << fixed << setprecision(6) << p.x << ' ' << p.y << '\n';

    return 0;
}