Cod sursa(job #3227429)

Utilizator code_blocksSpiridon Mihnea-Andrei code_blocks Data 30 aprilie 2024 14:39:17
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 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 pt
{
    double x, y;

    friend bool operator==(const pt& p1, const pt& p2)
    {
        return p1.x == p2.x && p1.y == p2.y;
    }

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

pt start(vector<pt>& ps)
{
    pt res(1000000001.0, 1000000001.0);

    for(auto& p : ps)
        if(p.y < res.y || (p.y == res.y && p.x < res.x))
            res = p;

    return res;
}

double cos(pt p)
{
    return (p.x - s.x) / (p.y - s.y);
}

bool right_turn(pt p1, pt p2, pt p3)
{
    return ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) < 0;
}

deque<pt> graham_scan(vector<pt>& ps)
{
    s = start(ps);

    auto cos_sort = [](pt a, pt b)
    {
        return cos(a) > cos(b);
    };

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

    deque<pt> dq;

    for(auto& p : ps)
    {
        dq.push_back(p);

        if(dq.size() >= 3)
        {
            while(right_turn(dq[dq.size() - 3], dq[dq.size() - 2], dq[dq.size() - 1]))
            {
                pt last = dq[dq.size() - 1];
                dq.pop_back();
                dq.pop_back();
                dq.push_back(last);

                if(dq.size() < 3)
                    break;
            }
        }
    }

    return dq;
}

int main()
{
    int n;

    vector<pt> ps;

    fin >> n;

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

    deque<pt> result = graham_scan(ps);

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

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

    return 0;
}