Cod sursa(job #3186228)

Utilizator RosuDragos123Rosu Dragos RosuDragos123 Data 22 decembrie 2023 09:54:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

struct nume
{
    double x, y;
};

nume v[120001];

double minx = 1e9, miny = 1e9;
vector <nume>st;

bool comp(nume a, nume b)
{
    return (-minx + a.x) * (-miny + b.y) > (-miny + a.y) * (-minx + b.x);
}

double determinant(nume a, nume b)
{
    return a.x * b.y - a.y * b.x;
}

int orientare(nume a, nume b, nume c)
{
    double val = determinant(a, b) + determinant(b, c) + determinant(c, a);
    if(val > 0)
        return 1;
    else
        if(val == 0)
            return 2;
        else
            return 3;
}

int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    double x, y;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i].x >> v[i].y;
        if(v[i].y < miny)
        {
            miny = v[i].y;
            minx = v[i].x;
            swap(v[1], v[i]);
        }
    }
    sort(v + 2, v + n + 1, comp);
    st.push_back(v[1]);
    st.push_back(v[2]);
    for(int i = 3; i <= n; i++)
    {
        while(st.size() > 1 && orientare(st[st.size() - 2], st[st.size() - 1], v[i]) != 1)
            st.pop_back();
        st.push_back(v[i]);
    }
    cout << st.size() << '\n';
    for(int i = 0; i < st.size(); i++)
    {
        cout << fixed << setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
    }
    return 0;
}