Cod sursa(job #3227451)

Utilizator code_blocksSpiridon Mihnea-Andrei code_blocks Data 30 aprilie 2024 17:54:57
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#include <algorithm>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <vector>
#include <immintrin.h>

using namespace std;

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

struct point
{
    long double x, y, angle;

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

// Formula se deduce din coordonata pe axa Oz
// a unui produs vectorial, anume P1P2 x P1P3.
inline 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;
}

// Folosit la determinarea punctului cel mai din
// stânga-jos. Apelul min_compare ar da eroare
// altfel.
inline 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.
inline bool pcompare2(point& p1, point& p2)
{
    return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}

inline bool acompare(point& p1, point& p2)
{
    return p1.angle < p2.angle;
}

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

    // 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ă.
    for(auto& p : ps)
        p.angle = atan2(p.y - s.y, p.x - s.x);
        // E mai rapid să memorăm unghiul în puncte,
        // decât să îl calculăm la fiecare comparație.

    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;
}