Cod sursa(job #3309761)

Utilizator mewcatPetru Boca mewcat Data 8 septembrie 2025 15:31:49
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>

using namespace std;

struct point
{
    double x;
    double y;
};

point a[120001]; //a[0] is the point we start with

stack<point> ans;
stack<point> aux;

double det(point a, point b, point c)
{
    double res = a.x * b.y + b.x * c.y + c.x * a.y;
    return res - a.y * b.x - b.y * c.x - c.y * a.x;
}

bool comp(point n, point m)
{
    double res = det(a[0], n, m);

    if (res > 0) {return 1;}
    if (res < 0) {return 0;}
    return n.x < m.x;
}

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

    int n = 0;
    point last;

    fin >> n >> a[0].x >> a[0].y;

    for (int i = 1; i < n; i++)
    {
        fin >> a[i].x >> a[i].y;

        if (a[i].x < a[0].x || (a[i].x == a[0].x && a[i].y < a[0].y))
        {
            swap(a[0], a[i]);
        }
    }

    a[n] = a[0]; //so it makes the full polygon

    sort(a + 1, a + n, comp);

    ans.push(a[0]);

    for (int i = 1; i <= n; i++)
    {
        while (ans.size() >= 2)
        {
            last = ans.top();
            ans.pop();

            if (det(ans.top(), last, a[i]) > 0) {ans.push(last); break;}
        }

        ans.push(a[i]);
    }



    while (!ans.empty())
    {
        aux.push(ans.top());
        ans.pop();
    }

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

    aux.pop();

    while (!aux.empty())
    {
        fout << setprecision(8) << fixed << aux.top().x << ' ' << aux.top().y << '\n';
        aux.pop();
    }
}